One option, obviously, is just to add another difficulty above Brutal. This would provide an added challenge, but it has the problem of being one-size-fits all. Since some commanders (like Zagara) are more affected by adjustments in the amount of enemy units coming in then others, it could be difficult or impossible to balance such an extra difficulty so that every commander gets a good challenge at high-masteries.
So here's my suggestion: have each map get a bunch of additional bonus objectives, with some randomization of which objectives appear in a given mission (for instance, a map might have 8 possible objectives, and 5 of them appear in a specific mission). You could then double the maximum XP earned from completing bonuses.
The result is that during a mission, commanders are free to take on as many bonuses as they can, keeping the experience challenging for everyone. If you have a bad ally or the map is poor for your commander, you can take on less bonuses while still trying to push yourself. If there's good synergy with your ally, you can go for all of the bonuses, and things will still be interesting.
The main drawback is that is would require a moderate amount of work from Blizzard on all the existing maps, but I think it would be worth it. Thoughts?