Here are some general tips from the WordPress Codex on this subject if you’re interested: http://codex.wordpress.org/Creating_an_Error_404_Page
I think some of things you’re describing aren’t really possible with the tools WordPress has by default. You can play with working with things like
$_SERVER['HTTP_REFERER'], but I’m not sure how much you can really do with these things. I don’t think you can easily get as specific of information as you’re wanting to.
It might be more realistic to think of some generic items to add like the last 5 posts from your blog, a search box to suggest searching for the page they’re looking for, maybe links to some of the more common pages on your site, etc.
Here are some functions that might be useful: