Hello,
actually it's not possible to add any custom HTML content to our Navigation controls unless you use our API. This means, you can use the following approach:
http://devnet.kentico.com/Forums.aspx?forumid=36&threadid=7311 which lies in modifying the final HTML layout of the CSS List Menu (yes, it is different from the CMS Menu you are referring to, but it is much better from the development point of view as well as from the SEO perspective - it is completely CSS driven).
On the other hand, it is possible to use the Repeater control and define any HTML layout you want in its transformation. This has a downside, however, because you need to create a custom functions to transformation which will handle the "navigation behavior". I mean, you need to highlight the current item, check the Show in navigation flag, etc.
It's definitely up to which way you go. Hope I helped to put you on the right track.
Best regards
Ondrej Vasil