Yes, you should be able to do that. If you check the web.xml of XWiki you should see:
<error-page>
<error-code>404</error-code>
<location>/bin/view/Main/DocumentDoesNotExist</location>
</error-page>
This means that you can edit this page and modify its content to do a redirect.
Actually there’s also a docdoesnotexist.vm
template file that you could override through a custom skin. But it’s more involved. I’d recommend creating or editing the Main.DocumentDoesNotExist page.