Move menu code to the template.php with the associate hook
You can add your code to custom module as custom block:

/**
 * Implements hook_block_info().
 */
function custom_block_block_info() {
  $blocks = array();
  $blocks['my_block'] = array(
    'info' =&gt; t('My Custom Block'),
  );      
  return $blocks;
}
/**
 * Implements hook_block_view().
 */
function custom_block_block_view($delta = '') {
  $block = array();      
  switch($delta) {
    case 'my_block' :
      $block['content'] = my_block_view();
      break;
  }      
  return $block;
}

/**
 * Custom function to assemble renderable array for block content.
 */
function my_block_view() {
  $output = '';
  $menu_array = menu_tree_all_data('main-menu');
  // Prepare your $output variable from $menu_array (like in your code).    
  $block = array(
    'menu' =&gt; array(
      '#type' =&gt; 'markup',
      '#markup' =&gt; $output,
    )
  );    
  return $block;
}


Then show this block in created region.