How to set up a "public" DNS server on linux server?

I need to set up a DNS server to be used with OpenVPN. I can not use conventional public DNS IPs (Like Google public DNS ones) because all of them are blocked in the ISPs where the OpenVPN clients are going to be used, hence need to define my own.

I appreciate your help.

P.S. I know how to define an authoritative DNS server using nsd3, but nsd3 is authoritative-only and I guess here what I need is a recursive DNS server. I chosen nsd3 after having enormous complexity issues with BIND9, so I hope you can suggest some solution that does not need BIND9.

P.S.2 I just found a nice comparison of DNS servers here on wiki. So I basically know what DNS servers CAN do the job. What I need is HOW to do so.

DNSMasq can do this: http://thekelleys.org.uk/dnsmasq/doc.html

For RHEL based distros, you can do something like this:

yum install -y dnsmasq
chkconfig dnsmasq on
service dnsmasq start

Then you should be able to point your clients at the IP of the server you just installed it on, and have DNS work nicely. Make sure the server has valid nameservers in /etc/resolv.conf though.