Why do I have a weird rendering issue only on 404.php caused by wp_nav_menu?

I’m not sure that this would be causing your problem, but one way you’re definitely Doing It Wrong is referencing menu instead of theme_location in your call to wp_nav_menu().

Let’s assumed you’ve registered your menu as “main-navigation” in functions.php, like such:

register_nav_menus( array(
    'main-navigation' => 'Main Navigation',
    'secondary-navigation' => 'Secondary Navigation'
) );

…then your wp_nav_menu() should reference this registered theme_location:

wp_nav_menu( array(
    'theme_location' => 'main-navigation',
    'menu_id'=> 'headernav',
    'menu_class'=>'navigate'
) );

There is no inherent reason that an error 404 template page should output the nav menu any differently than any other template. If the above doesn’t fix the problem, then we’ll need to see more of your 404.php markup, to diagnose the problem.

EDIT

Okay, I tried registering it and it had an effect: now the menu just doesn’t register.

Can you update your answer, and post your register_nav_menus() code?

Note: ensure that this function call is hooked into after_setup_theme; it normally goes in a theme_setup() function, hooked into after_setup_theme, like such:

function mytheme_setup() {

    // Register Nav Menu Locations
    register_nav_menus( array(
        'main-navigation' => 'Main Navigation',
        'secondary-navigation' => 'Secondary Navigation'
    ) );

    // Other Theme-setup functions may go here
}
add_action( 'after_setup_theme', 'mytheme_setup' );

So, post that code in your answer.

Also, once you’ve registered your Theme Locations, you need to go to Dashboard -> Appearance -> Menus, and ensure that you have applied your custom menu to the appropriate Theme Location.

EDIT 2

This is the code calling the menu from my header.php file:

<?php wp_nav_menu( array('theme_location' => 'main-navigation', 'menu' => 'Main Navigation','menu_id'=> 'headernav','menu_class'=>'navigate')); ?>

You are still passing menu and menu_id parameters to wp_nav_menu().

Why are you doing that? As I said above, that is Doing It Wrong. You need to pass only the theme_location parameter to wp_nav_menu(). WordPress then applies whatever menu is assigned via Dashboard -> Appearance -> Menus.

And this is the code from my 404.php file:

I’m not sure if it’s related, but your HTML markup is malformed. You have an opening <article> tag, and no corresponding, closing </article> tag.