I confess I've got no ideas that don't involve ugly hacks to my data and the template (such as storing a special variable in the array every time it changes level.

Don't think of it as an ugly hack. Think of it as one of life's many trade-offs. You're doing some set-up in code so that you don't have to contort your template.

If the depth of the tree you're dealing with can't be bounded, you can generate indentations in code, and do something like

  <tmpl_loop tree>
  <div class="leaf" style="margin-left: <tmpl_var margin>px"> ... </di
+v>
[download]

This has the upside of giving you fine-grain control over indentation, with the downside of that control being in code rather than in your template.

If the depth of the tree is bounded, you can move presentation into the stylesheet by generating a simple depth count in code. In the template, do something like

  <tmpl_loop tree>
  <div class="leaf depth<tmpl_var depth>"> ... </div>
[download]

and provide corresponding depth0, depth1, etc. targets in your stylesheet, with the generic style in leaf.