So, here's another answer ;-)
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;
}
In the callback function using current_path() will return the page which is producing the error.
Now that the page is created, 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.

Sample screenshot of the page not found page:

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.
which does not contain the URL of the page ;-)