Have you tried using template pages, HTML::Mason, or simply using here documents? Generally, when I am doing CGI which creates HTML that is quasi-dynamic (as in it looks the same, but certain values may change) and a non-Perl person is maintaining the HTML portion, I generally like to give them a template to use or a here doc. I have even used the __DATA__ token to allow them to do whatever they need to below it. But, using things like Mason will allow you to easily change HTML on many pages. I have also used Apache::Sandwich to allow for easy changes in headers and footers. I believe HTML::WWWTheme also does something of this nature (with nav bars and such), and Apache::SetWWWTheme. So, there are plenty of options out there.

Cheers,
KM