Skinning HTML sounds more like a job for XSLT than Perl per se. Given a structural XML document what you want to be able to do is transform it in a per user manner via one of a selection of templates into user xHTML.

The XSLT process will allow you to move content chunks around the page easily, and choose different CSS style sheets and so on.

AxKit or AxKit is probably the Perl solution for this, but may not be a solution for you given your server restrictions.

I must confess that I built my own templating solution that does almost what you want, and it works via the .htaccess file, but I plan to migrate to AxKit with time, as it's a more sopisticated solution.