Before you can use a nameserver it has to be created in the registry.
The current registrar for a given domain is the only one that can create the nameserver object in the registry (if it's a native domain in the TLD; if you wanted to register, say, a .ORG nameserver in the .COM/.NET registry, any registrar can do it). Presuming the parent domain (of the nameservers) is registered through GoDaddy you'd have to create the nameservers via GoDaddy. I'm not sure if/how GoDaddy supports that, as all of my nameservers are registered via my registrar. (And as I acquire domains through GoDaddy I transfer them out as soon as the 60-day hostage period is over.)
For the nameservers to work with [most] other registries, you need A records for them (since many registries don't provide DNS glue records).
So, assign IPs to the nameservers and set 'em up in their parent domain's DNS for starters. Then get the appropriate registrar to create them in the registry.
If you've not yet settled on nameserver software, I'd recommend Dan Bernstein's tinydns. See http://cr.yp.to
for details. It's small, fast, secure, and stable. It also doesn't have the defects that BIND has....