If you look in the wp_nav_menu() function, you see the items are written by walk_nav_menu_tree(), which calls Walker_Nav_Menu to do the work (unless you specified your own walker class). This class contains a method start_el() that is called for each menu item. In this function, you see that the classes are filtered through nav_menu_css_class and the id is filtered through nav_menu_item_id. So if you attach your own code to these hooks, you can change them to anything you want.
Submenus are always wrapped with <ul class="sub-menu">, the main wrapper can be changed via the menu_id and menu_class arguments.