I've done this recently for a large site. Basically they wanted to get rid of all the horrid things like font tags, a lot of tables, and generally tidy it up before applying CSS.

Using HTML Tidy (a fantastic tool), is a great start. Then I used HTML::TreeBuilder (my prefered HTML parser) to fix up a few more things.

Then I'd recommend stripping out the body of the document, then adding some sort of template for the top and the bottom. Then you can easily change the whole look of the site. Template-Toolkit or HTML::Template are both nice systems.