Patchwerk has no cards, but does not take fatigue damage by himself. He does, however, take fatigue damage if you make him draw cards. He uses a weapon that refreshes whenever it breaks, which has 4 damage with windfury, allowing it to strike twice every round. His Hero ability will destroy a minion and costs 4 mana for him.
How does this deck work against him?
This deck is built to keep him busy forcing him to trade against your Mirror Image aswell as Sludge Belcher, whilst freezing him with several freeze spells. Whenever you are about to face a smack causing lethal damage, there will ideally be a way to keep yourself alive, using Ice Block and Ice Barrier. Along with the taunts and freezes in the deck.
You always want to mulligan for the Acidic Swamp Ooze, since it costs him 3 mana to replenish his weapon after it has been destroyed. Along with this card you ideally want Mirror Image, aswell as some form of card draw. Coldlight Oracle works brilliantly, as it also causes 3 fatigue damage on him with the first murloc, and 5 fatigue damage when the 2nd murloc is dropped. Starting with Ice Lance or Frostbolt is also a good way to slow the fattie down. Optionally, you'll have Loot Hoarder, Novice Engineer and in even having an Ice Barrier can be good to secure a slow start for him.
This deck does not run Alexstrasza because it's simply too slow. Use your burst whenever you can and kill him as soon as possible. Keep a constant card draw to make sure you'll have the survival cards as a backup when needed.
If you are in need of any replacements in the deck, please do comment below and I'll reply with what I consider the best choice, along with adding it to the guide.