Hearthpwn

Just beat him, both players at 30hp. That's what happens when you know what you're doing.
But even if just one of you has a clue, it becomes much easier, so read this!

THE MULLIGAN.

As priest: Keep Arcane Golem, Coldlight Oracle, Lightwell,Loot Hoarder, Dancing Swords. I also like to keep light of the naaru, zombie chow and power word: shield because they are very flexible.
Paladin: Keep Dancing Swords. You can also keep Lorewalker Cho so you are sure to have him, he's the most important card of the deck. Refreshment Vendor is also a good keep if you like.

HOW TO PLAY:
Paladin: Turns 1-4, just pass and hero power or play dancing swords. Don't just throw a minibot out there as the only minion, he'll probably get assassinated anyway. Make a dude. You can drop a minibot later in the game as one extra target for the bombs that will then hit for 10 damage. Later in the game, a bot can soak TWO bombs. That's a lot of damage, so don't waste them. Don't waste your heals just to play on curve either, the priest has buff minions. Make dudes and don't attack with them. 

Turns 5+: Now it's time to get a little more aggressive. It's ok to spend a turn buffing a guy with divine shield and cashing in 7-10 damage on mechazod. Playing too passively and making dudes at this point is too slow, you need to wittle him down. As paladin you will deal most of the damage. Make sure you keep your Blessed Champion for as long as you can. The longer the game goes, the higher the chance that the priest will play Millhouse Manastorm and let you play Blessed Champion for free along with other spells.

It's also important to heal. Try to stay out of range of twice the attack that Mechazod has. 

The end game: Usually around turn 8-10 if you've both been playing right, you will have a hand full of spells and priest can drop milhouse and you can stack a ton of buffs on a minion and kill Mechazod. Trogzor can also be used that way, just drop him, shield him and then let paladin play 4-5 spells. That's usually enough.

As priest:
You're the combo enabler. Your entire early game is stuff that draws cards. So drop those and cycle through your deck until you find Milhouse or your buff minions.  DON'T ATTACK with loot hoarder. Let Mechazod kill them by wasting his powers. Same for Dancing Swords and Arcane Golem later in the game. If you see your paladin player sucks, try to keep Coldlight Oraclein hand for a big Milhouse or Trogg turn, or at least make sure the paladin has a minion he can buff and attack with when you pass the turn.

Lightwell is an important card for priest as it soaks up a ton of damage and heals you every turn for free. It's not uncommon to have a game where a Lightwell eats 20 damage.

General gameplay:
- Don't attack with any minions that aren't smashing in for over 4 damage. Exception is Dancing Sword, which you can trade if your partner is low on cards. Don't just trade in an arcane golem, it's more valuable that it eats a bomb or assassinate than it is to deal a measly 4 damage. Whether or not it's time to trade in your buffed minions can be a tough call. I wouldn't trade a minion for under 10 damage though.

-Don't leave buffed minions sitting in the open without attacking. They'll just die. Never waste buffs that way.

- Try to end the turn with divine shields on your big beaters.

-DON'T EVER HAVE 7 MINIONS ON YOUR SIDE OF THE BOARD AT THE END OF YOUR TURN. Mechazod will just clear your entire board for free. Who knows. 

-The coin: Don't waste it. Wait until you can buff a trogg or pass it back with Cho. Don't be the "coin+milhouse" turn 1 guy... I would never coin anything less than a 4 drop and even then, only if I'm desperate.

-Lorewalker Cho: Cho is the most important strategic card of this match. Mechazod will usually not target him with his "kill the lorewalker" ability on the first turn, but he will ALWAYS target him with that ability on the second. So that means that you can play lorewalker, play as many spells as you can and then protect lorewalker with a shield  so he doesn't die to bomb salvo. 
So the way you use him is you play as many spells as you can, pass the turn, and the other player plays as many  spells as he can KNOWING that Cho will die. So that means you can leave a huge buffed minion there for a turn and know it will live. It also means you can forego healing yourselves that turn because you cannot die.

Mechazod's Abilities:
At the end of each turn, he will switch places and use one of his free powers at random:
1- Bomb Salvo: He will deal his attack damage to 3 "random" ( I swear...) targets. This is why you never attack with small guys, better they eat a salvo to protect your face or your better minions. 
2- Overclock: He gains +2 attack
3- Double Zap: He hits both of you for his attack damage. Surprisingly he doesn't automatically use it when he has lethal, so don't concede. 
4- Assassinate: He will kill the minion with the highest attack. Use this to try and protect a valuable buff minion by playing a dancing swords or slightly buffing a crappier minion.
5- Kill the Lorewalker: He kills Cho. 

Good luck. Oh wait you don't need luck anymore brah YOU GOT DISS.

Example of a screenshot where two people played well ( even though paladin kept sending dudes to die into mechazod for no reason )

Quote from Rhyolth >>

Pretty complete guide. The only thing i might question is Mulliganing for Arcane Golem. Since most Paladin are retarded, they tend to waste many valuable spells too early, so, if you give them more mana,  they will burn those spells even faster...

Quote from PStrange >>

Hey, I think I was the guy playing with you in that shot.

Really good guide. That was my first try, so I didn't really know what the decks were about at the time; for most of the early/mid-game I figured the responsibility of doing enough damage to MZ in time was on me, hence the Zapp Brannigan approach.

Quote from LOLSugarHigh >>

The priest's hero power seems to be just as good as the paladin's since it essentially counters double zap, so I tend to spam it pretty often. Also there seem to be key turns where you can get a massive tempo swing, by abusing Gearmaster Mechazod's attack patterns. From experience, Gearmaster Mechazod always seems to kill Lorewalker Cho the turn after he's played, meaning you don't need to be afraid of any other spells that turn. Since the spells that the paladin plays are all buffs, it means you can buff the priest's minions without them being assassinated. Similarly, The Beast seems to be assassinated most of the times so you can use it as fodder to protect other minions so that they can be buffed after.

Quote from TehJumpingJawa >>

 It's not elaborate planning; it's the correct 'definitive' way to approach this challenge.

One thing that hasn't been mentioned is The Coin. The biggest (and most frequent) mistake I see is the coin being used for tempo.