The only way to do it without a referrer that I can think of would be to send them to a page that did a meta-refresh with a 0 second delay
Code:
<meta http-equiv="refresh" content="0;http://newsite.com/">
I don't believe that you can use javascript as it will show the original site.
so, to use the refresh, set your errordocument 404 to head to the page with your meta refresh, then, have the metarefresh page set to send them to the new page.
Using Redirect or mod_rewrite will send the referrer in the request.