Hearthpwn

Thanks for the reply! I will eventually have some dust, but I'm waiting to see how the meta settles and what nerfs might be coming in the future before I dust all my extra cards. The ones that seem kinda overpowered, I have kept my extra copies of just in case. Maybe I can afford to craft her eventually. I know there are some other decent decks she's used in, some rogue ones in particular. Rogue being the other class that uses Keleseth in a lot of decks, conveniently. Having her to help with the DK wincon is nice since that can be hard to pull off.

Getaway Kodo would be awfully situational but it might be an okay substitute to try to get a second Kelly buff... Hrmm.

Edit: Nvm. It's wild now. :(

Prince Keleseth decks are some of my favorite so I am really interested in giving this a try. The only cards I don't have are the Glass Knight, which seems pretty optional, and Zola. You list Zola as mandatory, but then rightly point out that she's really just there for an extra Keleseth buff if you get lucky. While I understand the power of that possibility, being rather RNG based, it doesn't seem mandatory and I can't really afford to craft her right now. Could you comment on this? I'll experiment with substitutions. Any advice is welcome. Cheers and good work!

Call the wahmbulance.

I've been at this for over two hours and still no luck on the evolution draw for SA or RE. However, I did tweak the deck in a manner that is evidently more powerful than that posted above. With no evolution whatsoever, I got LK to 18 health by turn 6 in one of my better draws/matches. The deck is provided below.

A bit about my adjustments. First and foremost, I have only one copy of Unstable Evolution and am unwilling to craft a second copy for a single PvE match. That said, it is abundantly clear to me that, with my version of the above deck, running two copies of the card would increase the likelihood of a win considerably, as you would not need to restart the match every time your first UE yielded no desirable results. 

The main difference about my deck lies in a few specific card substitutions. As the OP mentioned, you can run any 1 mana minions and make this deck work. But not all 1 mana minions are created equal. My version of the deck runs Feral Gibberer x2 and a Bloodlust. You do not need to mulligan for a gibberer, but when you get one early, man oh man, what a game changer. The gibberer allows you to maximize your card draw and keep a full board of minions every turn, giving you the highest amount of minions possible to evolve on your UE turn.

I also removed some of the other minions and added some more murlocs for better murloc synergy, and to allow the hungry crab to activate more often. The bloodlust, if available, can be used on turn 5 to bring LK within lethal range before you even have to think about evolving your minions. If you run two bloodlusts, you could potentially even kill him without needing the UE at all. 

Some other additions include Young Priestess to buff your minions' health and abusive sergeant and acherus veteran to provide some extra dmg potential. Overall, I think this deck performs much better than the above by providing some additional win conditions. Perhaps most importantly, win or lose, the deck is incredibly fun. 

Your optimal starting hand is UE, Gibberer and Bloodlust, imo. Other great starting cards are Fire Fly and any of the taunts, which you can play before they get nerfed to 1/1. Like the OP deck though, the most important thing is to have UE in your opening hand, and as long as I draw that, I do not reset.

Without further ado, here's the deck:

 ### Custom Shaman
# Class: Shaman
# Format: Standard
# Year of the Mammoth
#
# 2x (1) Abusive Sergeant
# 2x (1) Acherus Veteran
# 2x (1) Deadscale Knight
# 2x (1) Elven Archer
# 2x (1) Feral Gibberer
# 2x (1) Fire Fly
# 2x (1) Glacial Shard
# 2x (1) Grimscale Oracle
# 1x (1) Hungry Crab
# 2x (1) Murloc Tidecaller
# 2x (1) Runic Egg
# 2x (1) Shieldbearer
# 1x (1) Unstable Evolution
# 2x (1) Wax Elemental
# 1x (1) Young Dragonhawk
# 2x (1) Young Priestess
# 1x (5) Bloodlust
#
AAECAaoIBLsDgQWTCd/pAg3yAYUD2wP+A+IG4gyJtAKXwQLrwgKnzQKVzgLH0wLr4wIA
#
# To use this deck, copy it to your clipboard and create a new deck in Hearthstone

Wasn't counting attempts, but it was probably around 7 or so before I got him with my variation on this deck (see below). Not including restarts to get the right card draw, or attempts where he killed my tidecaller on the first second turn.

Got tidecaller out to start, was able to drop megasaur on turn 4 with four murlocs on the board thanks to a summon, and from there it was smooth sailing. Killed him on turn 6.

Here was my version, swapping out a few things from the above so I didn't have to craft anything:

### Custom Rogue
# Class: Rogue
# Format: Wild
#
# 2x (0) Counterfeit Coin
# 2x (1) Grimscale Oracle
# 2x (1) Hallucination
# 1x (1) Journey Below
# 2x (1) Murloc Tidecaller
# 2x (2) Bilefin Tidehunter
# 2x (2) Bluegill Warrior
# 2x (2) Murloc Tidehunter
# 2x (2) Rockpool Hunter
# 2x (3) Coldlight Oracle
# 1x (3) Coldlight Seer
# 1x (3) Fungal Enchanter
# 1x (3) Murloc Warleader
# 2x (3) Primalfin Lookout
# 1x (3) SI:7 Agent
# 1x (3) Zoobot
# 1x (4) Gentle MegasaurGentle Megasaur
# 1x (5) Finja, the Flying Star
# 1x (5) Menagerie Magician
# 1x (6) Corrupted Seer
#
AAEBAaIHCsUDpwjdCPmrApGtAuWyAp+3AuO+ArHCAofoAgrbA/4D4wXQB/gHiq0C9bsCncIChsQCm8gCAA==
#
# To use this deck, copy it to your clipboard and create a new deck in Hearthstone

Yeah, all these murloc decks are built to zerg him. I toyed around with the idea of trying to buff a weapon to use blade furry in the event you don't get him by turn 7, but it takes up too many card slots.

I have always drawn the scorn of the RNG gods, and while I keep getting close with this deck, I have fallen short after way more attempts than other posters claim. This is also after countless restarts because having bad RNG luck for life also means I can't draw a good opening hand to save my life. Oh, not exactly this deck, I should say. I crafted a few I didn't have and subbed in some other murlocs for some legendaries I don't have. I like having coldlight oracle in there for card draw.

Edit: I literally got him on the attempt after I wrote this comment. Always bitch and moan to get what you want. Drew tidecaller and shadowflame in my opening hand, so I knew this was my best shot yet. Drew Hooked Reaver (who I subbed in for the 4 mana legendary murloc) on turn 3 or so, so was able to drop him on turn 6 with 14 health to buff him to 7/7 with taunt. LK hit him with Shadowmourne, then I shadowflamed him to end phase 2 and killed him the same turn. Here's my deck (pretty cheap one too):

### Custom Warlock
# Class: Murlock
# Format: Wild
#
# 2x (1) Deadscale Knight
# 2x (1) Grimscale Oracle
# 1x (1) Mortal Coil
# 2x (1) Murloc Tidecaller
# 1x (1) Power Overwhelming
# 2x (2) Bilefin Tidehunter
# 1x (2) Blowgill Sniper
# 2x (2) Bluegill Warrior
# 2x (2) Murloc Tidehunter
# 2x (2) Rockpool Hunter
# 1x (3) Coldlight Oracle
# 1x (3) Coldlight Seer
# 1x (3) Fungal Enchanter
# 1x (3) Murloc Warleader
# 2x (3) Primalfin Lookout
# 2x (3) Vicious Fledgling
# 1x (4) Gentle Megasaur
# 1x (4) Hooked Reaver
# 1x (4) Seadevil Stinger
# 1x (4) Shadowflame
# 1x (6) Corrupted Seer
#
AAEBAcn1AgyTAcUDzgb4B6cIxAiRrQKtvALzvQKxwgL90AKH6AIJ2wP+A+MF0AeKrQKdwgKfwgKGxAKnzQIA
#
# To use this deck, copy it to your clipboard and create a new deck in Hearthstone

Not sure why my description isn't appearing, so I'll duplicate it as a comment. I built this deck to complete the Cry Havoc quest more quickly so it is full of battlecry minions. However, while completing the quest, I won 80% of my matches so I thought I'd save it and share it. Beat murloc paladin, jade druid, kingsbane rogue, among others.