Hearthpwn

The original lists where those of lionheart04 and Strifecro, that you can find here.

EDIT: NoxiousGLHF uploaded a video on his youtube channel with a list very similar to this, and he wins a lot! He runs 2 upgrades and Slam instead of a frothing and Blood to Ichor. Watch him if you want to see how this deck plays :)

I modified them a bit and the result got me on a 16 win streak from rank 4 to rank 1 5 stars, only one loss against the final boss, and then back to legend with 2 wins.

The MVPs of the deck are Bloodsail Cultist, which generates a lot of value for your weapon and is crazy easy to trigger with all the pirates, Ravaging Ghoul, which grants incredible tempo with board clears, and above all N'Zoth's First Mate. This last card is probably what makes the deck consistent, granting a turn 1-2-3 ping for no mana investment, enabling a 3/3 Bloodsail Raider on turn 2, and a cheap and effective way to trigger Bloodsail Cultist granting you a valuable 2/4 weapon. Crazy good.

Now for the other cards:

Upgrade! : Acts as a less good N'zoth's First Mate on turn one, but later it's a cheaper Captain Greenskin, or a Bloodsail Cultist without requirements. Works well in this deck, but I found that 2 is often overkill and a bad draw when you're topdecking.

Battle Rage : the best card draw for warriors in my opinion. It's a guaranteed cycle for 2 mana, and while that doesn't seem too great, its potential is so big that it's well worth it. If your starting hand is bad (aka filled with weapons, or no weapons at all - that happens sometimes!) even drawing 1 card is fine. Most of the time, you'll get 2 cards for 2 mana, which is great. But if you manage to combo this with ravaging ghoul, you probably won the game.

Blood To Ichor : I used Slam before, and that is still a viable option. Blood to Ichor is just so versatile, also on turn 1 with coin and N'zoth's First Mate, that I think it is the superior option. If you find that you need more card draw, run slam.

Sir Finley Mrrgglton : You won't find any use your warrior hero power, better pick another one! Best choice is Life Tap, followed by Fireblast and Shapeshift. Otherwise, any other bar paladin's hero power (dudes don't synergize well with ravaging ghoul) or rogue's, since you will almost always have a better weapon to use.

Captain Greenskin : acts as a free Upgrade! or Bloodsail Cultist, plus it's a pirate, so great sinergy.

Skycap'n Kragg : Adds another charger to the deck to grant reach and trades better than Kor'krons. You will usually cast this for 5, but 6 is fine too.

Malkorok : Underrated card. Great in topdecking, if you have this in hand with a weapon already equipped and your opponent is low on life, don't be afraid to go face. The result is usually a 3 attack weapon, and puts a decent body on the field for additional pressure. One out of 15 games or so you'll be screwed by Cursed Blade, so keep a N'zoth's First Mate if you have it in hand just in case!

Why not... :

Armorsmith/Cruel Taskmaster : gaining armor is not in your gameplan, and you already have plenty of pings with Ravaging Ghoul and N'zoth's First Mate.

Grommash Hellscream : no reliable activator, and adding those to the deck lowers the overall consistency. Kragg is used instead because of the potential for trading, and it costs much less. You can absolutely use Grom instead of Captain Kragg if you don't have it, but then you should add 2 Inner Rage (could cut a Frothing Berserker and an Execute) or alternatively run Blood to Ichor, but it might be hard to save it for Grom. In the end, it's mostly personal preference.

Revenge/Whirlwind : no need really. You already have Ravaging Ghoul.

Southsea Captain : giving your pirates +1/+1 is not really worth it, especially since you'll be hitting at most 2 pirates most of the time. Fierce Monkey is a way better 3 drop and adds a taunt to the deck.

Gorehowl : Gorehowl is a control tool, and this is more of a tempo deck. The main issue is that 1 durability if you go face to push for lethal: arcanite reaper is 3 more damage in that regard for 2 mana less, and is also easier to combo with bloodsail cultist.

What if I don't have...?

Captain Greenskin: can change with another Frothing Berserker or an Arathi Weaponsmith

Skycap'n Kragg: Grommash Hellscream (see above) or Leeroy Jenkins.

Malkorok: add another Arcanite Reaper.

 

Mulligan:

N'zoth's First Mate, Bloodsail Raider, Fiery War Axe. Keep Fierce Monkey and Dread Corsair on coin against aggro.

 

Remember, this is not an aggro deck, but a tempo/midrange deck. Don't go blindly for the face, and keep making advantageous trades helping your minions with your upgraded weapon, especially against zoo.