Advanced WordPress Menu Structure?

I am trying to get the following HTML output with a WordPress menu however with the default navmenu functions it provides it seems impossible. I tried storing the menu data in a array and just displaying it with my own code but I ran into issues with multiple submenu levels…. What would be the best way to do this been stuck on this for nearly 20 hours now.

Huge thanks in advance!!!!

WordPress Nav Menu Ussage Example

<?php

$defaults = array(
    'theme_location'  => '',
    'menu'            => '',
    'container'       => 'div',
    'container_class' => '',
    'container_id'    => '',
    'menu_class'      => 'menu',
    'menu_id'         => '',
    'echo'            => true,
    'fallback_cb'     => 'wp_page_menu',
    'before'          => '',
    'after'           => '',
    'link_before'     => '',
    'link_after'      => '',
    'items_wrap'      => '<ul id="%1$s" class="%2$s">%3$s</ul>',
    'depth'           => 0,
    'walker'          => ''
);

wp_nav_menu( $defaults );

?>

Menu structure I am trying to achieve

<!-- mp-menu -->
    <nav id="mp-menu" class="mp-menu">
        <div class="mp-level">
            <h2>All Categories</h2>
            <ul>
                <li class="icon icon-arrow-left">
                    <a class="icon icon-display" href="#">Devices</a>
                    <div class="mp-level">
                        <h2>Devices</h2>
                        <ul>
                            <li>
                                <a href="#">Mobile Phones</a>
                                <div class="mp-level">
                                    <h2>Mobile Phones</h2>
                                    <ul>
                                        <li><a href="#">Super Smart Phone</a></li>
                                        <li><a href="#">Thin Magic Mobile</a></li>
                                        <li><a href="#">Performance Crusher</a></li>
                                        <li><a href="#">Futuristic Experience</a></li>
                                    </ul>
                                </div>
                            </li>
                            <li>
                                <a class="icon icon-tv" href="#">Televisions</a>
                                <div class="mp-level">
                                    <h2>Televisions</h2>
                                    <ul>
                                        <li><a href="#">Flat Superscreen</a></li>
                                        <li><a href="#">Gigantic LED</a></li>
                                        <li><a href="#">Power Eater</a></li>
                                        <li><a href="#">3D Experience</a></li>
                                        <li><a href="#">Classic Comfort</a></li>
                                    </ul>
                                </div>
                            </li>
                            <li>
                                <a href="#">Cameras</a>
                                <div class="mp-level">
                                    <h2>Cameras</h2>
                                    <ul>
                                        <li><a href="#">Smart Shot</a></li>
                                        <li><a href="#">Power Shooter</a></li>
                                        <li><a href="#">Easy Photo Maker</a></li>
                                        <li><a href="#">Super Pixel</a></li>
                                    </ul>
                                </div>
                            </li>
                        </ul>
                    </div>
                </li>
                <li>
                    <a href="#">Magazines</a>
                    <div class="mp-level">
                        <h2>Magazines</h2>
                        <ul>
                            <li><a href="#">National Geographic</a></li>
                            <li><a href="#">Scientific American</a></li>
                            <li><a href="#">The Spectator</a></li>
                            <li><a href="#">The Rambler</a></li>
                            <li><a href="#">Physics World</a></li>
                            <li><a href="#">The New Scientist</a></li>
                        </ul>
                    </div>
                </li>
                <li><a href="#">Collections</a></li>
            </ul>
        </div>
    </nav>