Get an online and offline backup of your Exchange 2003 server and FSMO DC.

Add the new server into your existing 2003 organization. Update service
packs. Replicate your public folders to it. Move your user mail boxes to it.
Zero downtime involved, but the box gets a new name. Not a big deal since
Outlook should auto-update the server location in the profile once you move
the mailboxes.

Here is the detailed article:
http://support.microsoft.com/default.aspx?scid=kb;en-us;822931

Alternate method - Stop Exchange service, image hard disks and clone your
existing Exchange server to the new server hardware. Disconnect the old
server from the network. If the architectures are similar enough, it will
come up, redetect new hardware, and come online as if nothing happened.
Windows will probably want to be reactivated. If not, you'll run a repair
install from Windows 2003 CD, and then it will come up. Nothing to lose,
since your original server is intact. You'll need to update appropriate
drivers. Some downtime is involved, but you get to keep the name.

There you have it. :-)