I happen to be working on a project where I wanted to use a menu based on UL, LI, A tags, rather than the normal menu offered by DNN.
Unfortunately, there are a few problems with this. First off, this will only work in 5.0(.1) and up. Older versions simply do not support the "unordered list" menu. The NAV menu (and the older SOLPART menu) just "love" their tables. Jon Henning has introduced new menu CSS styling features, which give you more control over the classes assigned to tags for better skinning. But, I don't like these table based menus much, particularly because they use postbacks rather than straight "a" tags for links. "A" tags as links are better for SEO. But, Jon also added support for unordered list menus. These actually work great, AFTER some changes to the underlying javascript. Unfortunately, in its current incarnation (in 5.0.1), the unordered list menus are totally unskinnable because they use inline styles (for no apparent reason), which completely destroys any skinning you apply through CSS. But the javascript changes are simple enough.
Here is an image of the menu system I'm working on with just ul, li, a tags and some css styling.
Info about the new menu features can be found here: http://www.codeendeavors.com/Downloads.aspx
The bug report with a suggested source change is here: http://support.dotnetnuke.com/issue/ViewIssue.aspx?id=9771&PROJID=39
However, in any case, you can't inject your own html. It is all generated for you. You can only style the unordered list menus with CSS and have no other control over what is injected (actually, that may not be completely true, but I haven't tested it nor have I had the need to do so).
Other than that, your DNN built-in options are exhausted. But you could use the Telerik Radmenu or the free HouseMenu. I haven't used either, so this isn't really a recommendation, but I understand others use either with considerable success.