Merge XML documents
I know this is an old thread, but Project: Merge can do this for you. It can merge two XML files together, and can be run from the command line, so you can batch everything up together, run it and just resolve any conflicts (such as the changing attribute value of 'key' in your above example) manually with a few clicks. (You can tell it to run silently providing there are no conflicts.)
It can perform two-way and three-way comparisons of XML files and two-way and three-way merges. (Where a three-way operation assumes the two files being compared/merged have a common ancestor.)
Unsure as to whether you want to do this programatically or not.
Edit: Ah, I posted that before the Edit. Don't I look like an idiot now! ;)
If you just want to merge two files together, IBM have an XML Diff and Merge Tool, and there's also Altova's DiffDog.
If you like XSLT, there's a nice merge script I've used before at: Oliver's XSLT page
Check XmlCombiner which is a Java library that implements XML merging in exactly this way. It is loosely based on a similar functionality offered by plexus-utils library.
XmlCombiner default convention is to overwrite the overlapping attributes and elements. But the exact merging behavior can be altered using special 'combine.self' and 'combine.children' attributes.
Usage:
import org.atteo.xmlcombiner.XmlCombiner;
// create combiner
XmlCombiner combiner = new XmlCombiner();
// combine files
combiner.combine(firstFile);
combiner.combine(secondFile);
// store the result
combiner.buildDocument(resultFile);
Disclaimer: I am the author.