Q:

No navigation links on 404 pages

When I visit a page that does not exist, I expect to still see the primary and secondary links as on any other page, but what I get is no navigation links in the 404 page. See also No navigation links on 404 pages.
I have found a solution, but I am happy if something else can fix this (possibly without using extra modules).

A:

You can do it by defining a page in a custom module.
Create a page for the category "Page not found" using hook_menu().
function MODULE_menu() {
  $items['page-not-found'] = array(
    'title' => '',
    'page callback' => 'MODULE_page_not_found',
    'access callback' => TRUE,
  );
  return $items;
}

function MODULE_page_not_found() {
  drupal_set_title('Page not found');
  $cust_err = "";
  $cust_err = $cust_err . "The requested page " . current_path() . " could not be found";
  return $cust_err;
}

The page callback uses current_path() to return the path of the page causing the 404 error.
Go to Admin > Config > System > Site-information, and enter page-not-found (same name as defined in hook_menu) under Default 404 (not found) page.

Now the error page appears like in the following screenshot.

It is clear that it contains all the navigation links, and also the page URL producing the error (very similar to the original page not found). And the module mentioned in the answer above by @Nikhil will output "The requested page could not be found." but does not contain the URL of the page causing the error.

A:

There is a module to make this work 404 Navigation

On 404 Not Found error pages, Drupal will skip rendering of all the
  navigation links of your website for performance reasons*. Some of
  these include:
The "Primary links" block and any other menu links block. The Primary
  links and Secondary links of your theme.
  * Unless you have configured a "Default 404 (not found) page" on admin/config/system/site-information.

Also there is a Patch to fix this in D7.
In D8 See THIS Also THIS

A:

There are also good module alternatives:

Search 404

Instead of showing a standard "404 Page not found", this module performs a search on the keywords in the URL, e.g. if a user goes to http://example.com/does/not/exist, this module will do a search for "does not exist" and shows the result of the search instead of the 404 page. This should help retain visitors coming in from old URLs linked from other sites or from search indices.
Fast 404

Drupal has expensive 404 errors. On an 'average' site with an 'average' module load, you can be looking at 60-100MB of memory being consumed on your server to deliver a 404. Consider a page with a bad .gif link and a missing .css file. That page will generate 2 404s along with the actual load of the page. You are most likely looking at 180MB of memory to server that page rather than the 60MB it should take.

