Moving DNS servers can usually be done with no downtime. All you need to do is copy your current dns records to a new provider and then change the name servers. Keep your old DNS configuration up at least for a few days.

Gradually clients will switch over to the new DNS servers, but as long as both servers resolve to the same IP you should be fine.