If the themes were done in CSS instead of throwing markup around the page, it would be a trivial matter to switch between them, but...
It doesn't seem that anyone really thinks it should be there. If anyone changes their mind, I can't see how it'd be difficult at all for the page to just load a different stylesheet. style would need to be abstracted from content first, though.
Also if you're redoing things the template really should be moved from tables to divs, and cleaned up.