Add element inside main menu block, but outside navigation
To accomplish all your goals, you need to implement these three functions:


hook_preprocess_block()
theme_menu_tree()
theme_menu_link()


Create one template file for the block with your menu.

template.php

/**
 * Implements hook__preprocess_block().
 */
function YOURTHEME_preprocess_block(&amp;$variables, $hook) {
  // allow to use block templates depend on delta
  // example: delta = main-menu ; template file: block--main-menu.tpl.php
 if ($variables['block']-&gt;delta == 'main-menu') {
    $variables['theme_hook_suggestions'][] = 'block__' . str_replace('-', '_', $variables['block']-&gt;delta);
 } 
}

/**
 * Main menu
 * Implements theme__menu_tree().
 */
function YOURTHEME_menu_tree__main_menu($variables) {
    global $level;
    $div = ($level == 1) ? '&lt;div&gt; ... some div next to the main ul ... &lt;/div&gt;' : '';
    $ul = '&lt;ul class="menu"&gt;' . $variables['tree'] . '&lt;/ul&gt;' . $div;
    return $ul;
}

/**
 * Main menu
 * Implements theme__menu_link().
 */
function YOURTHEME_menu_link__main_menu($variables) {

  $element = $variables['element'];
  $title = $element['#title'];
  $sub_menu = '';

  // global menu level variable. 
  // within theme_menu_tree() at first level has always value = 1
  // but not here, that's why $depth will have to be defined separately
  global $level;
  $level = $element['#original_link']['depth'];

  // if you will need $depth, it must be defined separately
  // $depth = $element['#original_link']['depth']; 

  // submenu
  if ($element['#below']) {
    $sub_menu = drupal_render($element['#below']);
  }

  // link output
  $output = l($title, $element['#href'], $element['#localized_options']);

  // if link class is active, make li class as active too
  if(strpos($output,"active")&gt;0){
    $element['#attributes']['class'][] = "active";
  }

  $attr = drupal_attributes($element['#attributes']);
  return  '&lt;li' . $attr . '&gt;' . $output .$sub_menu . "&lt;/li&gt;\n";
}


block--main-menu.tpl.php

&lt;?php
/**
 * @file
 * theme's implementation to display a block with the main menu.
 */     
?&gt;
&lt;div id="main-navigation"&gt;
  &lt;div class="block block-system" id="block-system-main-menu"&gt;
    &lt;div class="block-inner clearfix"&gt;
      &lt;div class="content clearfix"&gt;
        &lt;?php print $content; ?&gt;
      &lt;/div&gt;
    &lt;/div&gt;
  &lt;/div&gt;
&lt;/div&gt;

&lt;!-- or a div added here would be ok --&gt;
&lt;div&gt; ... some div next to the main navigation div ... &lt;/div&gt;


Results