How to change HTML output of main menu When I output the main menu this is the html that gets generated:

&lt;ul id="main-menu" class="links inline clearfix"&gt;
    &lt;li class="menu-218 first active"&gt;&lt;a href="/drupal/" class="active"&gt;Home&lt;/a&gt;&lt;/li&gt;
    &lt;li class="menu-294"&gt;&lt;a href="/drupal/node/2"&gt;Page&lt;/a&gt;&lt;/li&gt;
    &lt;li class="menu-293 last"&gt;&lt;a href="/drupal/node/1"&gt;page&lt;/a&gt;&lt;/li&gt;
&lt;/ul&gt;


However I'd like to completely restructure the menu like this:

&lt;nav id="main-nav" class="animate"&gt;
            &lt;div class="grid__wrapper"&gt;
                &lt;div class="grid t--np nrp"&gt;
                    &lt;a class="button animate" href="#" title="Sign up"&gt;SIGN UP&lt;/a&gt;
                    &lt;a class="button animate" href="#" title="Login"&gt;LOGIN&lt;/a&gt;
                    &lt;a class="main-nav__button animate grid__item xl--1-5 l--1-5 sp s--tbp t--tbp" href="&lt;?php echo $front_page; ?&gt;"&gt;HOME&lt;/a&gt;
                    &lt;a class="main-nav__button animate grid__item xl--1-5 l--1-5 sp s--tbp t--tbp" href="#"&gt;LINK 1&lt;/a&gt;
                    &lt;a class="main-nav__button animate grid__item xl--1-5 l--1-5 sp s--tbp t--tbp" href="#"&gt;LINK 2&lt;/a&gt;
                    &lt;a class="main-nav__button animate grid__item xl--1-5 l--1-5 sp s--tbp t--tbp" href="#"&gt;LINK 3&lt;/a&gt;
                    &lt;a class="main-nav__button animate grid__item xl--1-5 l--1-5 sp s--tbp t--tbp" href="#"&gt;LINK 4&lt;/a&gt;
                &lt;/div&gt;
            &lt;/div&gt;
        &lt;/nav&gt;


How can I change the html output of the menu as well as the links inside?

Ideally I'd like to output any menus as a  element and be able to pass classes and an id to each one, the same also goes for the links inside.

Also the first two links in the menu are login and signup buttons which only display at certain screen sizes and have completely different classes to the rest of the menu links. Is this also possible to do?

I have tried altering the theme_menu_tree and theme_menu_link functions but am having no luck as I am somewhat of a beginner in PHP and Drupal.
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.