If you are only using them for DNS (and assuming their DNS works again) you can simply setup the new dns somewhere but not switch the DNS at your registrar. Until the dns is working at the new dns provider (and you would query it to find that out).
Example:
1) setup amixdomain.com at, say, zoneedit.com (not recommending them just using as an example).
2) Wait a bit, say several hours then use a dns utility like the one at kloth.net to query the two zoneedit.com dns servers directly. If both of them answer for your domain you are in good shape. I don't know what the lag is until zoneedit reloads their dns. It could be in a minute or it could take longer (which is why you can just wait).
Or you can use the OSX (or equivalent on other platforms) dig tool from the command line as follows, using ycombinator.com as an example:
Edit: What I meant to say was "if you have a mac open a terminal session and use dig" sorry for seeming to implying that dig is an OSX tool.
dig @NS1.EASYDNS.COM ycombinator.com 'A'
yc's servers are, so I picked one. You want to query all the dns servers:
Name Server: NS1.EASYDNS.COM
Name Server: NS2.EASYDNS.COM
Name Server: NS3.EASYDNS.ORG
Name Server: NS6.EASYDNS.NET
Name Server: REMOTE1.EASYDNS.COM
Name Server: REMOTE2.EASYDNS.COM
3) After the dns is active at zoneedit.com change the dns to the nameservers zoneedit.com gives you (change at your current registrar). You should have no downtime (since the old and new nameservers are answering with the same results.
In re-reading my comment I can see where someone would think I was implying that it was. Having worked with UNIX since V I am well aware of what you are saying. My mistake.
(What I was trying to say was "if you have a mac open a terminal session and use dig".)
Example:
1) setup amixdomain.com at, say, zoneedit.com (not recommending them just using as an example).
2) Wait a bit, say several hours then use a dns utility like the one at kloth.net to query the two zoneedit.com dns servers directly. If both of them answer for your domain you are in good shape. I don't know what the lag is until zoneedit reloads their dns. It could be in a minute or it could take longer (which is why you can just wait).
Or you can use the OSX (or equivalent on other platforms) dig tool from the command line as follows, using ycombinator.com as an example:
Edit: What I meant to say was "if you have a mac open a terminal session and use dig" sorry for seeming to implying that dig is an OSX tool.
dig @NS1.EASYDNS.COM ycombinator.com 'A'
yc's servers are, so I picked one. You want to query all the dns servers:
3) After the dns is active at zoneedit.com change the dns to the nameservers zoneedit.com gives you (change at your current registrar). You should have no downtime (since the old and new nameservers are answering with the same results.