How do I generate a custom menu/sub-menu system using wp_get_nav_menu_items in WordPress?

For anyone who tackles something similar here's my solution:

Quick code example on a gist

Here's the code on a github gist for anyone who wants to get in on the copy paste action.

TL;DR

TL;DR Loop over list, drill down if there's a sub menu, close if we reach the end of the sub menu and menu.

Complete Code explanation

Firstly get the menu items as a flat array:

<?php
$menu_name = 'main_nav';
$locations = get_nav_menu_locations();
$menu = wp_get_nav_menu_object( $locations[ $menu_name ] );
$menuitems = wp_get_nav_menu_items( $menu->term_id, array( 'order' => 'DESC' ) );
?>

Then iterate over the array of the menu items:

<nav>
<ul class="main-nav">
    <?php
    $count = 0;
    $submenu = false;

    foreach( $menuitems as $item ):
        // set up title and url
        $title = $item->title;
        $link = $item->url;

        // item does not have a parent so menu_item_parent equals 0 (false)
        if ( !$item->menu_item_parent ):

        // save this id for later comparison with sub-menu items
        $parent_id = $item->ID;
    ?>

Write the first parent item <li>:

    <li class="item">
        <a href="<?php echo $link; ?>" class="title">
            <?php echo $title; ?>
        </a>
    <?php endif; ?>

Check that this items' parent id matches the stored parent id:

        <?php if ( $parent_id == $item->menu_item_parent ): ?>

Start sub-menu <ul> and set $submenu flag to true for later referance:

            <?php if ( !$submenu ): $submenu = true; ?>
            <ul class="sub-menu">
            <?php endif; ?>

Write the sub-menu item:

                <li class="item">
                    <a href="<?php echo $link; ?>" class="title"><?php echo $title; ?></a>
                </li>

If the next item does not have the same parent id and we have a sub-menu declared then close the sub-menu <ul>

            <?php if ( $menuitems[ $count + 1 ]->menu_item_parent != $parent_id && $submenu ): ?>
            </ul>
            <?php $submenu = false; endif; ?>

        <?php endif; ?>

Again, if the next item in the array does not have the same parent id close the <li>

    <?php if ( $menuitems[ $count + 1 ]->menu_item_parent != $parent_id ): ?>
    </li>                           
    <?php $submenu = false; endif; ?>

<?php $count++; endforeach; ?>

  </ul>
</nav>

Your best bet is to make your own Walker class to tailor the output to your needs. Something like this:

class Excerpt_Walker extends Walker_Nav_Menu
{
    function start_el(&$output, $item, $depth, $args)
    {
        global $wp_query;
        $indent = ( $depth ) ? str_repeat( "\t", $depth ) : '';

        $class_names = $value = '';

        $classes = empty( $item->classes ) ? array() : (array) $item->classes;
        $classes[] = 'menu-item-' . $item->ID;

        $class_names = join( ' ', apply_filters( 'nav_menu_css_class', array_filter( $classes ), $item, $args ) );
        $class_names = ' class="' . esc_attr( $class_names ) . '"';

        $id = apply_filters( 'nav_menu_item_id', 'menu-item-'. $item->ID, $item, $args );
        $id = strlen( $id ) ? ' id="' . esc_attr( $id ) . '"' : '';

        $output .= $indent . '<li' . $id . $value . $class_names .'>';

        $attributes  = ! empty( $item->attr_title ) ? ' title="'  . esc_attr( $item->attr_title ) .'"' : '';
        $attributes .= ! empty( $item->target )     ? ' target="' . esc_attr( $item->target     ) .'"' : '';
        $attributes .= ! empty( $item->xfn )        ? ' rel="'    . esc_attr( $item->xfn        ) .'"' : '';
        $attributes .= ! empty( $item->url )        ? ' href="'   . esc_attr( $item->url        ) .'"' : '';

        $item_output = $args->before;
        $item_output .= '<a'. $attributes .'>';

        $item_output .= $args->link_before . apply_filters( 'the_title', $item->title, $item->ID ) . $args->link_after;

        /*GET THE EXCERPT*/
        $q = new WP_Query(array('post__in'=>$item->object_id));
        if($q->have_posts()) : while($q->have_posts()) : $q->the_post();
            $item_output .= '<span class="menu-excerpt">'.get_the_excerpt().'</span>';
        endwhile;endif;
        /*****************/

        $item_output .= '</a>';
        $item_output .= $args->after;

        $output .= apply_filters( 'walker_nav_menu_start_el', $item_output, $item, $depth, $args );
    }
}

And then call it like so:

<?php
wp_nav_menu(array('walker' => new Excerpt_Walker()));
?>

Everything before and after the GET THE EXCERPT marker in my example was a direct copy of the start_el function in wp-includes/nav-menu-template.php. My example uses WP_Query to determine if the post/page has an excerpt, and places the excerpt in between span tags after the link title.

An idea would be to make the span tags appear only upon hover, which can be done using CSS.

More information on Walkers here:

WP Nav Menu Codex

Using The Walker Class

Another Decent Example Using the Walker Class