Avoid clutter
Simplicity is hard, but it can help your users avoid a lot of effort and frustration. If you're unsure of what belongs on your 404 error page, concise, apologetic copy and a search input are more than enough to help users move forward.
It's certainly not a good practice to leave users without an "exit" from a 404 page, but it's just as bad to overwhelm them with a handful of links. As Nielsen's heuristic about minimalistic aesthetics points out, irrelevant information impedes visibility and can confuse users. Remember, less is more.