You have so far read a lot about why using several different templates can be a bad or a good idea. I suppose you known what you're doing there, or give it a good thought now after having read all the above posts.

Having said that, off the top of my hat I'd recommend HTML::Template for the task. It takes a bit of fiddling to get your mind around how it does the more compliacted things like loops and such, but once you know the drill it's a blast. Entering this into Super Search should give you plenty of information as well. There's even a review of the module by defyance.

You can still use Cookies to keep track of the users' preferred template, or whatever mechanism takes your fancy.

Hope this helps!