Don't really see this mentioned in the comments section, but: Bring a melee. Something melee dps. Bring it and have it hit hard. Guy has a lot of HP and very magic resistant. Paladin hate spell wouldn't land, nor any spell for that matter. No slows, like one shaman dot, practically nothing a Wizard Merc did, and the only thing Paladin could land was Stuns to keep aggro.
This dude does not bode well with magic classes, you're going to need a melee of some kind. Call up your local Rogue, Monk, or Berserker. This is the best suggestion I have. Unless you want to brute force it out with a bunch of magic classes. Choice is yours.