I've just done this very thing for a friends website, see my recent post about "A Records".
On the host where the website and emails currently reside, in the control panel change the A Record's ( both the www and @ A Records ) to point to the new hosts server IP. Don't touch the MX Records and the email will remain routed through the old host but you can now host the website on the new host.
If you simply change the name servers to point towards the new nameservers of the host you intend moving the site to, then everything gets routed through the new server including the email. Or you can do it the way Mark suggests.