How to get a cheap nameserver

A DNS hosting service sounds like what you're after:

http://en.wikipedia.org/wiki/DNS_hosting_service

DynDNS Custom appears to provide just that:

http://www.dyndns.com/services/dns/custom/

Side note: They were the only ones that could properly register my .name domain too :)

As long as you have a registered domain name, you can use http://freedns.afraid.org/ to provide free DNS services using your domain name. It worked well for me. There is no need for you to run your own DNS servers, not worth the hassle.

Just make sure your domain name's nameservers point to FreeDNS after you've signed up on their web site. You would change that at the web site of the company that sold you your domain name, the registrar.

Would this work for you? http://www.wtfdns.com/