Does that sound like Doing The Right Thing, or is there some nifty trick out there that I'm missing?
Pretty much the right thing. Code that is hard to test is often the better for a bit of refactoring. I think that you're right in your diagnosis. The problem you're having is due to having the presentation and logic too closely coupled. Separating it out into separate subroutines will help. Depending on the project it might be even more sensible to separate it out into a different class.
You might find writing your code test first helps. It seems weird at first but, in my experience, improves code quality a great deal.
As for testing show_template the technique you're after is mock objects. You make an object that pretends to be a template object, and then check that it was called with the appropriate parameters. Check out Automated software testing: emulation of interfaces using Test::MockObject and Micro Mocking: using local to help test subs for more info.
You may also find Unit Testing Generated HTML, WWW::Mechanize, HTTP::WebTest, Test::HTML::Content and Test::HTML::Lint of interest.