Sure. You could do the following:
Of course, you'll want to put the redirects in place before you change the DNS, but the above demonstrates the path a request for the old domain would take.
How you implement this depends on your server type. It should be simple using mod_rewrite on Apache, or the control panel or ISAPI filters on windows servers.
Technically, HTTP_HOST is only guaranteed to be defined for HTTP/1.1 requests. But this method will cover almost all requests, including almost all search engine spiders which advertise as HTTP/1.0, but do include the HTTP_HOST header in requests. If losing a very few of the HTTP/1.0 requests worries you, then you may want to set up a separate hosting account on the new server, and redirect from there.
Jim