Okay, I figure it out.
Instead of using wp_nav_menu, I use wp_list_categories which has more parameters that we can control.
So to not display empty menu, I use:
<?php wp_list_categories(array('taxonomy' => 'custom_tax','hide_empty' => '1','title_li' => '')); ?>
the hide_empty do the magic here.