Once you understand wht is the data structure, HTML::Template is really in your favour - you can create nested loops, ifs and includes. The problem is when you want to do something like taking a simple loop and print it in two columns, and then the design of the page will reflect in your code (I did this by creating a loop of rows inside a loop of collumns). I don't know if that's considered clean enough for you, but it's batter, IMO, than printing raw HTML, since the visual design is still left to the template
A related question is printing CGI fields: put them in the template or create them with CGI.pm? I mean:
<input type="text" value="<TMPL_VAR BlaBlaBla>" />
The answer depends on the complexity of the field (a hidden field is easy to put in the template, a dynamic n-level menu isn't) and the overall level of seperation you decided on - I usually separate as much as I can. Just look at it from the design / logic point of view: "Do I have to know what widget gave me this value?" usually not. Mostly you just have to know if the value is single, multiple choice, etc. but not how it got there.
Hope this helps
My public key