If you are familiar with pretty much any programming language, you might find it easier to use a tree-based (DOM) XML parser, then walk the DOM tree and manipulate it in one or more passes, and write the result out to disk. It's pretty much just like manipulating HTML elements with JavaScript code, if you've ever done that.
If you don't know any programming languages, then XSLT is probably the better of those two choices. Then again, PHP, Perl, Python, and Ruby are all relatively easy to learn (with PHP being probably the most straightforward in terms of having a fairly lightweight and consistent syntax), so maybe it's time to pick up a new hobby.