This is about themeing but it would need an app. I remember using something on the computer to change it a long time ago but I think that was a shell replacement (Can't think of the name, sorry). I then remembered something that I gave a shot. I think this is more of a "cover up" for Windows XP. It's called Window Blinds Stardock.com - Your Edge In Software
If that's not feasable, I am just thinking there has to be a way to make an app that just covers up stock. Like Handcent. It doesn't remove the stock messenger, I just turned off notifications for the stock messenger and use Handcent.
Couldn't there be an app to do the same thing for theming. Without rooting. If possible, it would be easier to maintain because non rooted users can't change from the stock ROM so there would be no ROM specific support needed.