How to change HTML output of main menu
Most likely that your theme renders them menu either in theme_preprocess_page() in its template.php and passing it page.tpl.php. That's how Garland does it:

https://api.drupal.org/api/drupal/themes%21garland%21template.php/function/garland_preprocess_page/7

https://api.drupal.org/api/drupal/includes%21theme.inc/function/theme_links/7

Given your question, you're most likely going to end up with a custom theme, which is normal for most sites. The best way to tackle this is to change the logic in preprocess_page to set it up how you like. 

That's more sustainable and specific than altering or overriding theme_links() globally in module-space.