Steven you may need to look at a third party menu provider to have an image based dynamic menu - if I am reading this the same way Salar may be
You can get a more flexible menu here - http://www.telerik.com - but at a cost.
However, if you want a little icon on the left hand side - as well as an image affect then you can achieve this with the solpart menu functions extending the active menu classes which are required in both the ascx file and the css class. The image on the left of the menu is simply an icon put in at the page level which is displayed. Not many people use it but it is possible.
You cannot have different colors across the whole menu but you can have different colours on the active state, hover state, sub menu state and active sub menu state using Solpart Menu. I have a skin that although doesn't depict all these fetaures very well that has a mix of the sub menu items. http://www.ninasfreeskins.com/designaway/vertical-menu.aspx it's from dnn 2 days and I confess it's not been updated or checked with the latest dnn 4 version but will get round to that when I have time.
If you want to have the whole menu to be completely different you will need the third party controls such as telerik or compontent art -
I know that in the future on skincovered.com we will have some extended menus - using Armand Datema's graphical menu options, but it's not completed yet - it will allow you to create buttons on the fly - and save them, and the menu will pick it up - but you have to create the buttons as you go so while it will be dynamic, it doesn't do it automatically upon page creation, however, those looking for a something a little different will be prepared to go that extra step.
Having said all this - I would like to point out, as I've done in lots of posts, and I am pretty sure that Salar will agree, that it takes a strong person to walk away from trying to create something that really isn't dnn friendly - it's not that it can't be done, it's just that so much time can be wasted on a few lines of code and it's easy to forget the other great aspects of dnn. And this is just a few words from someone who has spent more hours than I wish to publicly acknowledge trying to get things to do what I think they should do.
I hope this gives you more insight to some work arounds.
Nina Meiers