Base64 with shuffled alphabet
A well-formed XML document is subject to all sorts of constraints.

You can incorporate these constraints into a function that checks a base64 substitution key by looking for invalid syntax, such as improperly nested tags, or a tag name containing control characters, white space, or any of the characters !"#$%&amp;'()*+,/;&lt;=&gt;?@[\]^`{|}~, or that starts with a dot, hyphen or numeral.

Combine this with a backtracking search algorithm, and with a bit of luck you should obtain a solution within a reasonable amount of time.

If it turns out to be too slow, there are other assumptions you could make. For example, most XML documents use only printable ASCII characters in their tag names, and often contain white space after closing tags.