I did it, with the help of this answer: how to sort categories as they are shown in admin?

New code:

<?php 
 
 // Create get_string_between function
 function get_string_between($string, $start, $end){
    $string = ' ' . $string;
    $ini = strpos($string, $start);
    if ($ini == 0) return '';
    $ini += strlen($start);
    $len = strpos($string, $end, $ini) - $ini;
    return substr($string, $ini, $len);
 }
 
 // Get menu items
 $menu = $this->getLayout()->createBlock('cms/block')->setBlockId('main_menu')->toHtml();
 $menu = get_string_between($menu, '<p class="menu">', '</p>');
 $menuParts = explode("--", $menu);
 $isCategory = false;
 
 // $testArray = array();
 
 // Set integer variables
 $i = 0;
 $i2 = 0;
 $level = 0;
 
 // Start menu
 echo '<nav id="nav">';
 
 if ( !empty($menuParts) )
 {
 
     echo '<ol class="nav-primary">';
     
     foreach ( $menuParts as $part )
     { 
     ?>
        
        <?php // Create level 0 menu items ?>     
         <li class="level<?php echo $level; ?> nav-<?php echo $i;
         
             if ( $i == 0 ) 
             { 
                echo ' first';
             }
             else if ( $i == (count($menuParts) - 1) ) 
             { 
                 echo ' last';
             } 
             
             $fullUrl = get_string_between($part, '<a', '/a>');
             
             // Dynamic Link
             if ( strpos($part, 'widget') !== false )
             {
                 $name = get_string_between($fullUrl, '<span>', '</span>');
                 $_category = Mage::getResourceModel('catalog/category_collection')
                        ->addFieldToFilter('name', $name)
                        ->getFirstItem();
                        
                 // Category Link
                 if ( $_category->getId() != null )
                 {
                     $_catUrl = $_category->getUrl();                 
                     $_catName = $_category->getName();
                    
                     if ( $_category->hasChildren() )
                     { 
                         echo ' parent';
                         $_catHasChildren = 'has-children';
                     }
                     else
                     {
                         $_catHasChildren = '';
                     }
                     
                     $isCategory = true;
                 }
                 // CMS Page Link
                 else
                 {
                    $_catUrl = get_string_between($fullUrl, 'href="', '">');
                    $_catHasChildren = '';
                    $_catName = get_string_between($fullUrl, '<span>', '</span>');
                    
                    $isCategory = false;
                 }
             }
             // Static Link
             else 
             {
                $_catUrl = get_string_between($fullUrl, 'href="', '">');
                $_catHasChildren = '';
                $_catName = get_string_between($fullUrl, '">', '<');
                
                $isCategory = false;
             }
             
             // array_push($testArray, $fullUrl);
             
         ?>"> 
         
                
            <?php // Echo anchor tag ?>
            <a href="<?php echo $_catUrl ?>" class="level<?php echo $level; ?> <?php echo $_catHasChildren; ?>"><?php echo $_catName ?></a>
            
            <?php
            // Start level 1 menu
            if ( $isCategory && $_category->hasChildren()  )
            { 
            ?>            
                
                <ul class="level<?php echo $level; ?>">
                    <?php
                    $subCats = $_category->getChildrenCategories();
                    $subCatIds = $subCats->toArray(array('entity_id'));
                    ?>
                    
                    <li class="level<?php echo $level; ?> view-all"><a class="level<?php echo $level; ?>" href="<?php echo $_category->getUrl(); ?>"><?php echo $this->__('See all'); ?> <?php echo $name; ?></a></li>
                    
                    <?php
                    foreach( $subCatIds as $subCatId )
                    {
                        $sub_cat = Mage::getModel('catalog/category')->load($subCatId);
                        if ( $sub_cat->getIsActive())
                        {
                            $catUrl = $sub_cat->getURL();
                            $catname = $sub_cat->getName();
                            ?>
                            
                            <li class="level<?php echo $level; ?><?php
                                echo ' nav-' . $i . '-' . $i2;
                                
                                if ( $i2 == 0 )
                                {
                                    echo ' first';
                                }
                                else if ( $i2 == (count($subCatIds) - 1) )
                                {
                                    echo ' last';
                                }
                            ?>">
                                <a class="level<?php echo $level; ?>" href="<?php echo $catUrl; ?>">
                                    <?php echo $catname; ?>
                                </a>
                                
                            </li>
                            <?php 
                            $i2++;
                        }
                        
                    } ?>
                    <li class="level<?php echo $level; ?> back-link"><a class="level<?php echo $level; ?>" href="#"><?php echo $this->__('Back'); ?></a></li>
                    <?php $level = 0; ?>
                </ul>
                
            <?php }
            
            ?>
            
         </li>
         <?php $i++; ?>
     <?php }
     echo '</ol>';
 }
 echo '</nav>';

?>

Is it best practice tho?