Darkmoon Murloc Paladin

The archtype only got a few commons this expansion, but at least it got something unlike in Scholomance. Also, these new additions feel really helpful (got from diamond 10-5). The deck is budget-ish, but I wouldn't craft it because Scalelord rotates next expansion and it kind of glues the deck together.  

The new cards, as I said, are few and cheap, but important: 

Wriggling Horror: Not the best in turn 2 unless you have the coin and a couple of 1-drops, but you will have two targets most of the time. A 2 mana 4/3 is unsurprisingly strong in aggro decks, specially when it gives you two damage of charge. 

Prize Vendor: Still figuring out the numbers of each card (before the new cards arrived this deck used to run a weapon package with Truesilvers and Hoarders, and the Vendor used to be a Hench-Clan Hogsteed), but I think one copy is fine. I've chosen this over the Hogsteed because the Crocolisk body makes it easier to drop buffs on it and the card draw is nice, but you can change it for something else if you are playing against decks that demand faster answers (like, I don't know, Totem Shaman) or don't like the symmetrical effect (this deck doesn't run out of fuel that fast compared to other aggro decks anyway, mainly thanks to Underlight Angling Rod and the last newcomer)

Redscale Dragontamer: The strongest new addition. Like the Vendor, it gives you a nice Crocolisk body for you to buff and card advantage; specifically, it tutors Scalelord, the top end of your curve. Except Warrior, pretty much no deck won't be able to answer your board on turn 5 if you play the Scalelord onto a bunch of murlocs, and now you can get access to it way more consistently. 

The deck is pretty straightforward: mulligan for a curve that includes at least a 1 and 2-drop, keep stuff like Underlight Angling Rod and Coldlight Seer depending on if you have the Coin and/or early sticky minions such as Imprisoned Sungill or Murmy. Go face as much as you can but don't be afraid to value trade with other aggro decks if you manage to stick some minions on the board and have buffs in hand: you'll usually take over the game if that's the case.

If you want to make the deck cheaper, you don't really need the Murgur Murgurgle: you aim to finish the game 1 or 2 turns after a Scalelord on curve, and the Prime will be irrelevant almost always. You'll mostly just use him as a resilient minion you can buff early on and value trade with, so you can change him for a second Prize Vendor to fulfill that role and get your Scalelords on curve more consistently.