I know this is 3 years old, but you can do exactly what you say, in wp_nav_menu set the items_wrap attribute:
wp_nav_menu(
array(
'theme_location' => 'menu',
'items_wrap' => '<div class="div-inserted-inside-wrapper-before-ul">New div inserted</div><ul id="%1$s" class="%2$s">%3$s</ul>'
)
);
So this extra has been included in items_wrap:
<div class="div-inserted-inside-wrapper-before-ul">New div inserted</div>
btw the default for items_wrap is:
wp_nav_menu(
array(
'theme_location' => 'menu',
'items_wrap' => '<ul id="%1$s" class="%2$s">%3$s</ul>'
)
);
That will end up with html output like this (a custom div inside wrapping div, before menu ul):
<div id="menu-wrapper" class="menu-wrapper">
<div class="div-inserted-inside-wrapper-before-ul">New div inserted</div>
<ul id="menu" class="menu">
<li class="menu-item">
<a title="Menu Item" href="#">Menu Item</a>
</li>
...
</ul>
</div>