Totally override a menu
Take a look at theme_menu_tree() and theme_menu_link(). It should be all you need. 

Sorry for the lack of examples, but theme_menu_tree is rather self-explanatory, and the page for theme_menu_link provides several examples.