How to rewrite the output of wordpress nav menu?

You could either try a custom walker as suggested above, or try to work it out via the number of invaluable arguments for the wp_nav_menu function. There are several parameters that you can use in order to change the container, list item ot entry classes, ids or even HTML tags. See if that would cause less troubles for adapting the standard menu to your custom variant (or would require just a cosmetic change).