HUGE and FUN viable warrior deck which is easy to climb with once you get around the unusual playstyle. 70% Winrate from rank 5 to Legend. Enjoy! I'm not claiming this deck is suitable for Top 100 Legend or competitive, but its worked for me up to 187 Legend.
Woriking on full guide. Sorry for the delay, should be up in a few days.
Winrate update (13.6.2018): 216 games played and winrate is at 67%. This is played over 2 accounts. The first one i went from Rank 5 to Legend with 70% winrate and the second one i went from Rank 10 to Rank 2 (Not sure about the winrate here, probably around 63%).
The most important thing to keep in mind is that you never want to keep minions, having them in hand ruins the whole point of the recruit part of the deck.
Druid: Forge of Souls, Brawl, Gather Your Party and Shield Block.
Hunter: Most of the time i keep Forge of Souls, Warpath, Gather Your Party and Shield Block. BUT if i'm feeling lucky and feel it in my bones that it's Spell Hunter, I keep Bring It On, Warpath, Forge of Souls and Gather Your Party.
Mage: Shield Block, Forge of Souls, Iron Hide and Warpath.
Paladin: Forge of Souls, Warpath, Shield Block and Gather Your Party.
Priest: Brawl, Forge of Souls, Gather Your Party and Shield Block. I keep Dead Man's Hand if in opening hand.
Rogue: Shield Block, Shield Slam, Forge of Souls and Warpath.
Shaman: Warpath, Forge of Souls, Gather Your Party and Shield Slam.
Warlock: Forge of Souls, Shield Block, Gather Your Party and Brawl.
Warrior: Forge of Souls, Gather Your Party, Shield Block and Dead Man's Hand.
Woecleaver CAN NOT be replaced. you can replace all of the legendary minions to other high cost- high value minions that doesn't rely on Battlecry to be effective. Its very important to note that you can't put in low cost minions like silences etc. That depend on Battlecry to be effective as these might get recruited and ruin the steam and power of the deck. I would also not recommend to swap out Scourgelord Garrosh as it is a huge survival tool and great board clear and Grommash Hellscream, as the burst is quite important.
To watch the deck in play: https://www.twitch.tv/arnoldthehobbit