I've been trying to modify the code from the HTML::Template tutorial.

Did you notice the "Miscelaneous Options" section in the HTML::Template POD? If you set   loop_context_vars => 1 when you create the HTML::Parser instance, you'll get a couple of magic variables that you can use inside of <TMPL_LOOP> for doing odd/even stuff. It lets you write

  <TMPL_LOOP stuff>
    <TMPL_IF NAME="__ODD__">
    Odd stuff
    <TMPL_ELSE>
    Even stuff.
    </TMPL_IF>
  </TMPL_LOOP>
[download]

Depending on what you're doing, handling odd/even in the template can be a lot cleaner than trying to do it in code.