It's not necessary to have two hosting accounts. Two servers are initially easier to conceptualize until you understand what mod_rewrite does. Last I remember, GoDaddy web hosting doesn't let you use mod_rewrite, but I am not sure of that.
I would build the site on a new hosting account that has mod_rewrite enabled, create your .htaccess file with the necessary redirects, and then, with both sites up and running, make your necessary DNS changes to point both sets of A-records to the new IP... and, again, then use mod_rewrite to rewrite requests for the old domain to the new one. Since both the old site and the new site are up and running at once, the propogation should be seamless.
Keep the new IP account blocked so it can't be spidered until you're ready to throw the switch.
If you also need to change registrars, the migration might be glitchy for a day or so, but in my experience it's not nearly as bad now as it was years ago.
...you should add the domain to virtual host entries in httpd.conf
This gets into levels above my expertise. Many hosting companies won't let you touch httpd.conf if you have a shared server. Some hosts will make such changes for you, and some charge for that. And with some kinds of hosting accounts, particularly I think if you have a unique IP for your domain and make the changes the way I suggest, it's not necessary to go into httpd.conf. We need someone more familiar with Apache servers, though, to discuss that.
There are other issues related to moving to a new domain that are touched on in this current discussion... [webmasterworld.com
While not about changing domains, the thread touches on many of the issues you'll need to pay attention to.