Legend Proof: http://i.imgur.com/4ezvbUt.jpg
This deck is Taunt Warrior and it is a bit different than other ones that you might see.
I utilize Dirty Rat to cuck quest rogues AND other quest warriors by pulling out cards that can effectively finish their quest. This decklist also runs Acolyte of Pain that has great synergy with Whirlwind and Ravaging Ghoul as cycling for taunts makes finishing the quest that much easier.
A must have for this deck is Deathwing. You might cry when he's sitting in your hand like a brick but he will save your ass in those control matchups that go to fatigue, I promise you.
There's not too much to this deck: fight for board control, use your removal/resources efficiently while trying not to be too wasteful; finish your quest then when the time is right become one with the Rag and start lighting up those insects!
Paladin - Murloc paladin is a tough matchup because he can drop murlocs down faster than you can crush them and when he starts buffing them it can be over by turn 5. Mulligan for Fiery War Axe and Stonehill Defender. Pray that you get a Brawl by turn 5.
Priest - Dragon priest is one of the tougher decks and if you waste your Executes too early you will be out of resources and if you can't contest with minions you won't have board control. Your priest opponent will likely run potion of madness and cabal priest so you will likely lose your acolyte and alley armorsmith. Count his shadow word pains/deaths and if it gets to fatigue Deathwing can be your savior when the time is right.
Rogue - similar to pirate warrior but Dirty Rat and removal is key here.
Hunter - mulligan your quest and get some removal and it will be a breeze. You just want to kill everything he drops and have removal for his Tundra Rhino, then just survive until your taunt minions do the work for you.
Mage - Burn Mage is surprisingly easy, just stack armor so his burn isn't enough. Dirty Rat is very useful.