I had a similar project and I wound up using HTML::Treebuilder. Since I'm not familiar with HTML::Parser, I'm not sure if this is better or worse than your approach.

With Treebuilder, you do apperations on html viewed as a tree. You identify the elements you want with the $element->lookdown method, specifying criteria. For simple criteria, this can just be tag is blee, attribute a is bloo, attribute b is blah. For more complicated criteria you can write a subroutine.

Then you build up the replacement html with another subroutine, and do the replacement with $element->replace(new element). I'm not looking at the perldoc as I write this so I probably made some mistakes on the syntax, but that's the general idea.

Worked for me!