I don't know how extensive you want your re-theming to be. However if it could be CSS-only you could use this approach:
Store the CSS files for the different themes in the Style Library or in 14 Hive.
Create a list/table that stores the user and their chosen theme.
Write a feature and custom application page to allow the user to change their theme.
Write a control that does a lookup on the list against the current user and obtains the a reference to the corresponding CSS file in the Style Library or in 14 hive. The control would then output the CssRegistration and CssLink controls to the page for this file.
Add this control to the master page so it executes on every page (caching should be added).
I can't see why this wouldn't be supportable by Microsoft as you're only changing CSS.