I decided to go for legend with my Spiteful Mage and got stuck around rank 3. After making a few key changes I got to legend with a record of 15-3, so I'm sharing!
Showcase (Thanks to kiwiinbacon)
+ Hunter (Kathrena deathrattle can be tricky though)
~ Rogue (Baku can be tricky but any other is easy)
- Mage (ouch)
- Warrior (but still winnable)
Basic mulligan: If you don't get Prince Keleseth in your starting hand, try to find enough 1-drops to play minions on both turn 1 and 2 (1x Fire Fly + 1x Argent Squire/Glacial Shard is ideal). If turns 1-2 are covered, keep one of the stronger 3 drops (Tar Creeper/Coldwraith) and so on.
Vs aggro: Keep a Tar Creeper no matter what.
Guide (in progress)
Before I go into deck-specific strats, I want to mention a few things about a couple of cards in the deck.
Coldwraith - This is the card that people have questioned the most. As I have posted in the comments, 90% of the time this card is played for the 3/4 body alone, and the draw should be seen as an added bonus if it happens. A strong curve is much more important than drawing, so never sacrifice tempo to set up a freeze combo for Coldwraith.
If you feel uncomfortable almost always missing the combo, there are several (untested) alternatives: Blackwald Pixie(double Jaina/normal ping), Nightmare Amalgam(Extra Jaina lifesteal), Vicious Fledgling(Probably too hard to defend), Thunder Lizard (probably good but inconsistent).
Frost Lich Jaina - Looking at the stats of the deck I see that 20% of people are holding on to Jaina in the mulligan. Jaina is not core to this deck, she is there as a Plan B to save you against aggro or in case you can't beat control mid-game. Spiteful Summoner is a better choice if you feel the need to hold on to something big.
Feel free to experiment with the deck and post your results. I will add any user-made guides to the description.
+10 upvotes for mulligans! ✔
+20 upvotes for guide! ✔ (in progress)