I recall once I had to do similar things to a messy XHTML document, and XML::XSH came in pretty handy. It is an XML editing shell written in Perl with a number of utility shell commands to ease the work with structured data like XML, HTML, etc. It can do node insertions and deletions, filtering and manipulation of attributes (which might fit your needs here) and similar stuff with a very easy syntax.
in reply to Parsing XML/HTML
Here is a nice tutorial on how to use XML::XSH from our beloved merlyn...