Currently when I hit a 404 URL Magento serves the custom 404 page I set up under CMS -> Sites (noRoute) while staying at the 404 URL.
What I want is that instead Magento should redirect to the page www.mydomain.de/404.
How can this be done?
You can extend the reroute action in your own module and then, inside the controller code, have:
header('HTTP/1.0 404 Not Found'); die;
That should do the job.
Here is a tutorial on extending the reroute action: