Without looking at what you're doing, it's hard to offer suggestions to your specific site.

We use HTML::Template (and CGI::Application - check it out!) for all our CGI work, and at this point, we're pretty consistent in how we use it. The biggest help is that since you can put HTML::Template logic in your include files, we generally create top & bottom containers (headers, navigation, footers) with their own logic (if needed), and include them on all the other templates. The additional benefit is that you can then create a sub to populate the containers, and call it as needed, cleaning up your code further.

I've found that anything as small as a table, if used on multiple pages, makes a good candidate for an include. It means that both in your HTML and your perl, you'll have only one place to maintain it. Generally a good thing.

So don't try and make a single template as generic as possible - it makes things too complex and difficult to maintain. Take the common elements in all your pages, split them out into includes. The end result will be a lot cleaner.