If the other hosting company allows you to upload directly to their server before your nameserver settings have changed, do so. That way the switch will be near seamless, with no downtime of your site.
Four will work, but all you really need is only two. It will check the primary nameserver, and if it doesn't respond - it will go to the next one. In your case of four nameservers, it will check #1, then #2, then #3, then #4 - if none of those responds, a 404 is displayed.