Hearthpwn

Who would have thought this was possible? 
I have an about 60% win rate now with this deck over 30 tries. 

Btw: DO NOT WASTE YOUR TIME WITH MILL DECKS AGAINST HIM. ALSO, READ THIS GUIDE ON HOW TO PLAY THE DECK.

=====================================
Replacements:

Deck Core: 2x Arcane golem, 2x arcanite reaper, 2x death's bite, 2x execute, 2x cruel taskmaster, 2x kor kron elite, 2x fiery war axe, 2x shield block, 2x antique healbot, 2x shieldmaiden, 2x mortal strike

The epics don't really matter that much individually but they offer very good any-size removal. They can all just as easily win you the game as sit in your hand doing nothing. I'd say that bouncing blade is probably the best, followed by shield slam and then crush.  

Other considerations: Mind control tech, big game hunter, cleave, whirlwind, sylvannas. 

General Strategy:

Nefarius is as evil as he is stupid. How you beat him is simply to remove all of his minions and never play any of your own. This will cause him to stop playing cards eventually and just burn the rest of his deck as he sits there with a 10 card hand doing nothing even though he probably has lethal on you since most of his hand is direct damage.  This is why mill strategies are bad. If you feed him cards, he will overwhelm you with the minions in his deck before you can remove them.

STRATEGY:

Mulligan for: Fiery war axe, ironbeak owl, execute, bouncing blade, arcane golem

1. Phase 1: Surviving ( turn 3,4,5 ) this is the time to remove his minions while taking as little damage as possible. This is where Brawl can randomly win the game. Arcane golem and bouncing blade are very strong here as they are just about the only removal that costs 3 and that will take out a guy ( like the 5/4 ). This is huge as it often means saving you 10+ life. Early you MUST kill as many minions as you can every turn. This means spending all your mana and trying to at least set up his guys to die ( for instance set a 5/5 to 5/1 by running a kor kron into it knowing it will die to death's bite trigger etc ).

These are the crucial turns where he will almost always bring you down to less than 10health before he just stalls out. If he draws just a little bit too many minions, you lose. It's about a 50-50 and it can depend on the Ragnaros card.

As a general rule, try to only have one minion out at a time, as if you have two he will simply flamestrike/cleave them while empties his hand. This is bad, you don't want this.

2. Phase 2: He's out of minions. Eventually, once his hand is usually at 4-5 cards, he will spend a turn playing just one or no minions. This means you've won. Now check how much health you have left. If you'are close to 4-5 and have low removal, play healbots and shieldmaidens. Otherwise, just armor up, then equip a death's bite / arcanite reaper and pass. In this phase, he will simply play one minion per turn if he draws one, so keep in mind that he could play a giant twilight drake or a 9/9 crusher. Keep your executes / shield slams / bouncing blades for those guys and use smaller chargers and weapons for the smaller minions. NEVER DROP TO 4, OR 8 IF YOU CAN HELP IT. DON'T PLAY ANY MINIONS AT THIS STAGE UNLESS YOU NEED TO HEAL.

3. Phase 3: Deck burning. Now as he keeps playing his topdecked minion each turn, he will also get a random warrior card which clogs his hand. He will also draw spells. In that case, he will play nothing and pass. Eventually he will be at 10 cards in hand and pass the turn. This is the time to just go face with weapons and burn useless cards like revenge so you don't have more than 10 cards in hand. NO MATTER WHAT THOUGH, DO NOT PLAY ANY MINIONS. He will just burn the rest of his deck so just wait even if you have 10 cards in hand and start burning your own cards. Doesn't matter. Just armor up and pass. 

4. Final phase: Fatigue war. When he's burned the last card in his deck, you've usually won. Now you have two options: Play it fast or play it slow. If you're really low on life ( like 15 or less total life + armor ) you should play it fast. So just drop your weakest minion ( ONE AT A TIME, NEVER MORE THAN ONE, EVER ) first ( like ironbeak owl and cruel taskmaster ) so he starts to burn his good removal. You will see that eventually he will run out of removal and you'll stick like an arcane golem or healbot on the field. This will allow you to deal a good chunk of damage because he drops to about 10-12 armor, at which point he will remember that he has shield slam ( lol ).  Then you simply continue playing minions, ONE AT A TIME. Usually you can stick a kor kron elite or  a shieldmaiden that he can't remove and then even if you started out at low HP, you'll destroy him as he fatigues for 5-6+ a turn while you armor up and hit him for 5. Even if he started out at 80hp you'll destroy him with 30+ armor remaining on your side.

Hope this helps!