Not sure there is a magic bullet for this. Sounds like you're in for some work, and I'd advise that whatever you do be as reusable as possible in the face of future changes.
You might want to consider using xproc (via Calabash or some other engine) to create an XML pipeline whereby you detect and pass in changes of an XSD into an XSL (perhaps keeping to the convention of one XSL per XSD, to retain your sanity), and then said XSLs take those changes and handle them for all XML files bound by the XSD whose changes are being handled at the moment. Breaking all these into sub-transformations within the pipeline could be possible, and might make things more reusable in the future.
Inside the XSLs you're likely looking at doing something like:
- for all changes to be made
- for each XML
- match/add/delete per element and/or attribute to implement change
One way to represent the changes to be made in some sort of standard format is as an incoming list of operations to perform and associated elements/attrs to act upon (maybe set it up as key/value pairs). Each operation could be a string (add, delete, convert) or a numeric code. You then traverse the list of ops and associated elements and trigger matches to accommodate.
This is all somewhat abstract because I have no idea of the scope or depth of changes you need to make. I'm really just thinking out loud here. You might just have to knuckle down and do some serious one-time work, then implement some sort of change control process to make sure things don't get out of hand in the future.
Hope this helps. Good luck!