Custom 404 - menu disappears
If you can accept using a module for this, rather than a theme override, you should be able to use CustomError:


  This module allows the site admin to create custom error pages for HTTP status codes 403 (access denied) and 404 (not found), without the need to create nodes for each of them.


Just to make sure I've understood the use case: You write:


  Since I only wan't to change the actual message that is displayed when receiving a 404 page


This message is by default "Page not found  The requested page "..." could not be found. ".  I think CustomError' will reproduce the standard message unless you override this - but it may something about your use case that I have not understood.