I have reached legend this month with Mecha'thun just today. After the nerfs Hunter is more popular, but Rastakhan gave an interesting weapon to priests which is often overlooked against Greater Emerald Spellstone. And that is Auchenai Phantasm + Circle of Healing, combined with still existing Wild Pyromancer comboes it adds just enough survivability to Mecha'thun priest to outlast aggression until Psychic Scream turns. The important part is that new Auchenai gets destroyed by Hemet, Jungle Hunter. And control decks are almost free wins for you, and deck is often faster than other combo decks. It is still vulnerable to burn from hand, so tempo mages are the biggest problem even without Mana Wyrm, but luckily those are rare.
The main combo is just standard one:
1) Reckless Experimenter
2) Coffin Crusher
3) Ticking Abomination x2
4) play any 0 mana spells or 2 mana deathrattles you can keep leftover (Experimenter gives them discount of 3, so they are 0 mana, though be aware of fatigue before keeping them, as you don't want draws usually, so if you can afford that still scream them into opponents deck)
5) End turn = win
Make sure that your deck is empty and you have only Mecha'thun in hand.
Against Priest, Druid and Warrior just hard mulligan Hemet, because that is the only card that matters against most of the decks this 3 classes have. If you already have Hemet then always keep Psychic Scream, because those are really bad to have in the bottom of the deck and early game minion can be also kept if you have Hemet, just so that you can keep the occupied from going face.
Against other classes still always keep Hemet, but as other 6 classes have some more aggressive decks so keep Auchenai Phantasm and/or Circle of Healing, keep Northshire Cleric, consider keeping Wild Pyromancer especially on coin.
Against slow decks (combo/control)
They don't pressure you so playing Hemet is soon as possible is the name of the game. If you have hemet in hand, consider holding back card draw if you don't have no combo pieces in hand, because ideally you want 3 cards in deck after playing Hemet so that ideally on turn 10 you take 1 damage of fatigue. Because if you don't do that what can screw you over is Psychic scream in the bottom of the deck, 4 cards in deck is fine if you drew both Psychic Screams already. If you don't have Hemet power draw, just make sure to not mill unless you have all 5 combo pieces in hand, if you do, then feel free to mill yourself especially if you are on 9-10 mana already.
As you probably will be pressured play out all the draw minions as they come when you can... Hold your board clears until they have many at least 3-4 medium sized minions or 5-6 small minions on board or until the turn right before you going to play Hemet. Also coin is a valuable resource, you rarely coin out Hemet in this match ups, as you usually will die if you do Hemet on turn 5... instead use coin to activate wild pyromancer, or coin out the Psychic scream and then play Hemet after you screamed, usually that would be a better use of coin. Don't use your healing spells too early, activating wild pyromancer for an extra tick is often important.
The most notable interaction from Rastakhan is Auchenai Phantasm interaction. it is not an aura effect, but "this turn" effect, so if Auchenai dies your healing still does damage. here are some examples of what you can do with it:
Auchenai + Circle x2 is a board clear for 8 damage for just 2 mana, but requires 3 cards, so it rarely happens, but still is good, you can even ping something and kill a single guy with 10 health (like a 4/10 Twilight Drake for example). or you can play auchenai, regenerate on Devilsaur egg and then Circle and ping Devilsaur for example.
Do remember that if you want to heal yourself with excess mana then do that first. And that Thalnos will increase damage of the spells.
Then pyromancer clears, if no minion on opponent's side are damaged you can start by doing a tick of pyromancer with Circle of Healing first. Also you always want to cast Power Word: Shield on Pyromancers, so that he doesn't die as easily and you can chain spells more easily. If you don't have Power Word: Shield yet, then consider starting chain with Shadow Visions to search for one.
When using Shadow Visions, one of the best spells are third Psychic Scream because you want to scream on turns 7,8 and 9 quiet often, but have only 2 screams in deck itself. Other than that it is situational, but Circle of Healing is always good as it is 0 mana so you can just play it out on combo turn even if you never get to play it otherwise and also allows for crazy comboes sometimes with Northshire or Auchenai. other than that it is situational depending on what you want to cast next. Generally divine spirit is also good. Power word: shield is usually bad unless you plan to cast it immidiately or preparing for a wild pyromancer turn on next turn, because otherwise it is hard to get rid of sometimes.
Also try to not attack into hunter secrets if possible, because getting one of you minions with Freezing Trap usually delays your combo by a turn or 2 which might be enough for hunter to just kill you. Other secrets are usually irrelevant, but attacking opponent's face is not relevant for this deck, so might as well not trigger secrets off all classes that trigger of attacking face by never attacking face if secret is up.
Acolyte of pain is one of more clunky cards as it is hard to get rid from your hand after you Hemet, so try to just play him onto board whenever you can, even if gets silence removal it is still better than him being stuck in hand on turn 9 (because you don't have enough mana to play him and scream on same turn)
Hold back Psychic screams sometimes against other priest, as you want to be the last guy to use one...
From Screenshot above you can see that I was against a some slow mage deck and my opponent was dumpster legend so not very committed, so just conceded when I did couple of power draw turns with my Northshire, which is not interesting. So here instead some of my adventures are rank 1. Including win streak from yesterday.
https://hsreplay.net/replay/LKjJoFAtYjKqnEYjjyBd69 - win against Odd Rogue, see how to time board clears.
https://hsreplay.net/replay/PAW2XhV3HCY24wCotAgQh5 - a loss against other priest, but shows why Acolyte of Pain is clunky...
https://hsreplay.net/replay/yUNwV63NyUU6DEZLk2D6wQ - win against Deathrattle Rogue
https://hsreplay.net/replay/Aaywu3sCrL6o87yVQCWxh3 - win against Odd Warrior, well it is pratically free win, but this game demonstrates why holding back draws for some power draw after Hemet is good. (opponent just conceded when I did that)
https://hsreplay.net/replay/qA2EhRAiKxtbngvZaXkkE8 - win against mech paladin.
https://hsreplay.net/replay/ujWSkoaJj4ncCMjxLwRAxF - win against Gallery priest. Shows this Psychic Scream back and force...
https://hsreplay.net/replay/h3ZUcBrfiA6LYZxMGQQCS7 - lost against Even Paladin... Was kinda forced to do board clears too early, but probably should have held back somewhere, but got a bit unlucky as he got really good lich king cards too...
Of course there were more wins and losses... overall winrate for me was 59% from rank 3 until i reached Legend...