Drupal - Advanced menu theming in Drupal 7

Drupal's implementation of menus is a bit special, It doesn't always work the way it seems it should.

You can take a look at the core implementation of template_preprocess_page() to how the Main Menu links are added as a variable to the page template. You have to drill down a bit in the API docs, but the function you want to call in your implementation of theme_preprocess_page() is menu_navigation_links(), which will return an array of links in the menu.

Looking at line 106 of Drupal core's page.tpl.php file, you can see how the main menu links are themed in the template by calling the theme() function with a hook of 'links__system_main_menu'.

Theoretically, this implementation should be able to be duplicated with a custom menu by following the standard naming conventions. So, in template.php, you could have:

function THEMENAME_preprocess_page(&$variables){
  $variables['custom_menu'] = menu_navigation_links('menu-custom-menu');
}

function THEMENAME_links__menu_custom_menu(&$variables){
 //custom theme function here
}

and in page.tpl.php, you would add something like this:

<?php print theme('links__menu_custom_menu', array('links' => $custom_menu, 'attributes' => array('id' => 'custom-menu', 'class' => array('links', 'inline', 'clearfix')), 'heading' => t('Custom menu'))); ?>

However, adding the custom menu as a variable on your page template is not necessary. You could easily place the custom menu's block into a desired region via the Drupal admin interface. Also, you could change the site's settings for the Main Menu source, effectively replacing the default $main_menu variable in page.tpl.php with your custom menu.

EDIT: I am just seeing your addition about your end goal being to just add some custom html to the menu items for icons. Depending on how you are adding these icons, there are a couple different Drupal module options.

Menu Icons - allows you to upload an image via the Menu item's settings and automatically generates CSS (customizable via a template) that adds the image as a background on the menu item.

Menu Attributes - allows you to add a custom class to each menu item via its settings in the admin. Once a unique class is added to each menu item, you could use CSS to add an icon to the menu item or use javascript to inject the additional HTML into the menu item.