Hearthpwn

Deck I used to beat heroic Patchwerk. Mulligan for Ooze, and "sustainers", which basically means cheap taunts, Healing Touch and/or Claw. Coined turn 1 Ooze nets you 8 hp worth of time, since he can't resummon the weapon until turn 3. Besides turn 1, the Oozes are best used after turn 3 for they make Patchy use the mana for resummoning the weapon instead of using the hero power.

Since the fight consists of Patchy beating your face or taunters and later turns sniping one taunter/minion from the board, all you need to be concerned about is getting it's hp down faster than yours reach 0. The taunter chosen seems to be random, since I've had him kill a taunted up Ooze instead of Druid of the Claw. Your hp will drop in 4hp chunks, so hero power, heal and Claw/Bite your total hp + armor to 9 or more. Taunt the board up (two taunters at a time in later turns when Patchy is able to snipe the first one with hero power) and go to town on his patched face. You can't over extend, so just play out your hand as effectively as possible.

Violet Teachers are there (in theory, on either one of the kills I didn't draw them) to give you more mileage from spells with small bodies that you can emergency taunt, since every taunter above 1 on board will buy you 4hp and cuts Patchys hp down when it swings to it. They are untested though, so if they feel weak, feel free to replace them with something else. Earthen Ring Farseer could be really nice replacement, since it will go above the magical 4 toughness when taunted up with Mark of the Wild.

Taunters with more than 4 hp are the best since they can take two swings, and thus get to deal their damage twice. Remember though that the first one will get hero powered past turn 4 (unless you've destroyed his weapon, which he will always resummon first). Harrison Jones on recently resummoned weapon is just godly, but don't wait to cast it if there is a weapon in play. The turns on Patchys side go as follows:

Turns 1 and 2: Swing to face/taunters if the weapon is there, otherwise just pass turn.

Turn 3: Swing to face/taunters, if the weapon is destroyed: resummon it and proceed to swing face.

Turns 4 to 6: Swing to face/taunters, and nuke one minion with hero power, unless the weapon needs resummoning.

Past turn 7 Patchy will resummon weapon if needed and Hero Power away, so you'd better be close to killing him already.

So on turns 1-3 you should be using to build the board/mana a bit and on minimum gain 3 hp or armor to be out of turn 4 weapon swings reach (4 times 8 equals 32, go figure). So first 3 hp/armor gained means extra turn of weapon swings survived and after that it's 8 hp/armor for a turn. Past turn 4 you'll need to have two taunters up for each turn for the weapon swings, or gain enough hp or armor to survive. One taunter per turn is fine on turns when he needs to recast the weapon, so use those Oozes + Harrison Jones wisely. Each time you gain 8 hp / armor, you have bought yourself another turn.

Good luck and have fun.