wp_nav_menu and its fallback

The default fallback menu is created with wp_page_menu() function and if you want to customize it the you need to create your own fallback function :

function my_fallback_menu(){
   $args =array('whatever');
   wp_page_menu($args);
}

and then call that function in your wp_nav_menu call as the fallback:

wp_nav_menu(array(
    'theme_location' => 'mainnav',
    'container' => 'nav',
    'container_id' => 'mainnav',
    'container_class' => 'clearfix',
    'depth' => 4,
    'fallback_cb' => 'my_fallback_menu'
)); 

to check if a menu exists you can use has_nav_menu() function:

if (has_nav_menu( 'mainnav' )){
    //display the menu
}else{
    //no menu yet do something else
}

and to simplify the things even more you can just call the menu and set the fallback to false:

wp_nav_menu(array(
    'theme_location' => 'mainnav',
    'container' => 'nav',
    'container_id' => 'mainnav',
    'container_class' => 'clearfix',
    'depth' => 4,
    'fallback_cb' => false
));