I had written up a long comment about what to do, but this more or less nails it. Here's what I had to say from a more DNS centric perspective:

You can do this with no downtime if you don't have any other outside circumstances forcing your hand, such as your current web hosting expiring very soon.

Hint: find a web based DNS test tool. Google "DNS Report", the dnsstuff.com one used to be really nice but they got too ambitious with a bunch of crap on their site and I think it's a pay service now, the dnscolos.com one looks like it's pretty good, I can't tell about the checkdns.net one. Also if you'll be running your own DNS services (as opposed to outsourcing them where someone else maintains the hosts) you'll want to find a DNS server package that has good documentation and good tutorials. My personal bias is toward BIND to get things going right away and then migrate to something else (PowerDNS, maybe) after you get it working because BIND is very, um, featureful, and needs updated a lot. :)

As you've determined, DNS servers are like web servers for static content in that you can have two different sets of them running that think they're the owners of the domain. If you give your new servers data identical to the old ones, it won't matter which set is serving your records, as the client will end up with the same data.

There is a notion, as you've probably read by now, of a TTL, or Time-To-Live. This is a number that goes along side your DNS response and tells the computer that your record will be staying the same for the next X seconds, so it doesn't have to ask again. Managing this in all of the records is crucial to a smooth migration.

You need to know the TTL of your current records. It sounds like you have a UNIXy machine at your disposal in the VPS. Log in and execute:

dig -t NS google.com

You will see a bunch of goop, but you really only care about:

;; ANSWER SECTION:
google.com. 345600 IN NS ns4.google.com.
...

The 345600 is the number of seconds that the current name servers can be cached out on the internet. You won't be able to cleanly move your services faster than that if you don't control your current nameservers.

dig google.com @ns4.google.com

;; ANSWER SECTION:
google.com. 300 IN A 64.233.187.99
...

if you care about your email you're going to need to track your MX records as well, using:

dig -t MX google.com @ns4.google.com

wherein you will see:

;; ANSWER SECTION:
google.com. 10800 IN MX 10 smtp4.google.com.
...

;; ADDITIONAL SECTION:
smtp1.google.com. 3600 IN A 209.85.237.25

Again, in all of these answers field #2 (300, 10800, 3600) are the number of seconds that each record type (A, MX, A for smtp) are cacheable by servers across the internet. You will control these on your new server.

You will want to set the TTL of your A (and MX) records very low on your new server. 300 seconds would be a 5 minute migration from site to site.

Once you have your DNS servers properly set up (dig example.com @new.srvr.ip.addr) update your information with your registrar, giving them your new name servers as the only nameservers for the account. Then the NS TTL countdown begins. In our google test case you'd have four days before you could move the site cleanly. I'm not sure if all registrars push updates hourly or not -- it used to be that they only did it once daily. I'd wait NS TTL + 24 hours to be safe, if you have the time.

Once everyone is visiting your new name servers, you now can migrate your non-DNS servers. All you need to do is properly update the IP addresses, which can include incrementing the zone serial numbers if you're using a BIND-alike. After updating the A (and MX) IPs you have their old TTL seconds to wait before the migration is complete and everyone should be viewing things on your new servers.

After your migration is complete you can (at your option) turn your TTLs back up so that the load is reduced on your DNS servers. It's not really critical to do this, but it can carry you through if your DNS servers ever have a short network connectivity outage.

Good luck.

I've glossed over a bunch of stuff (some root NS stuff, DNS is badly implemented in a lot of places, some things don't honor TTLs, and so on) but these steps should be enough to do an upgrade in the common case with no problems.