Royal Mukla Duels Paladin

I'm having good success and a ton of fun with this build. 6-8 wins in my runs with it, which is about where I max out as a player. 

King Mukla shines! In the early games (when you're more likely to draw him) as a 5/5 for 3 or coined on 2 he can run away with the game for you. The +1/+1 buff from Bananas are less relevant with a hero power that can reduce a minion to 3/3 and his legendary rarity provides another target for the weapon to pull. If that's not enough positive synergy, he can also be resurrected by Rally! for a second chance to smash opponents.

I have gone back and forth on a few cards here so there's definitely room to experiment. Blessing of Might vs. Blessing of Authority - the lower cost buff works so well in the early matches. Tirion Fordring vs. Turalyon, the Tenured - lLove the taunt but hate losing the Greatsword if the opponent kills Tirion, while Turalyon's rush can negate any nasty minion your opponent has. Hammer of Wrath and Claw Machine are two that I keep going back to for draw and to help control the board. 

Always, always, always keep the Royal Greatsword if you get it at mulligan.