301 Redirect from Old Domain and Old Host

I will be cancelling services with my old host and thus my old site will disappear and I cannot simply serve the 301 redirect in the htaccess file on the old host.

I have since tried pointing the name servers to my new host where the new site is being hosted. I keep being told that I need to import the entire old site to the new host before the redirects will work. Is this true? Is there any way around this? The domains are purchased through Network solutions and it doesn't appear they have the ability to do the redirect themselves like some other registrars can. Any advice is much appreciated.