You should have the providers overlap and test the new site to make sure it is working (You can just make an entry in your hosts file with the new IP to test the new site).
If you have only static content, keep them both live while you make the DNS and change and it will never be down. If you have dynamic content, when you make the DNS change, have the old site forward requests to the new at the same time you make the DNS change. You could do that with iptables if you are using Linux.
You might also try to lower your DNS TTL value for the site a little while prior to the cutover.