Working with raw data is always a bit dirty. The clean approach to do that would probably be to implement an own widget, that does exactly what you want it to do.
You can learn more about using the Widget API here: http://codex.wordpress.org/Widgets_API
There are also some great examples there. Not that hard to understand.
To start off, you can basically copypaste the code of the default WP_Nav_Menu_Widget from default-widgets.php (lines 1298 to 1363) into you theme (I would suggest an own file, which you require from the functions.php) and start customizing it.
But to come back to Christophs answer: The Walker API is very powerful and learning it is defiantly worth it, if you want to do fancy stuff with navigations, comments, etc. pp.