I feel that the deck is pretty tight right now. I'd only ever consider switching Rotten Applebaum and Shadowflame. In that case, I believe that Sludge Belcher and Dark Pact would be suitable replacements.
An overall tip: be mindful of getting too greedy trying to build a massive Bloodreaver Gul'dan turn. If you have stabilized you can maybe delay it a turn or two to add a Mal'Ganis or a Voidlord to the fray, but otherwise it's a good idea to get that overpowered Hero Power as early as possible.
vs. Control Decks
Be mindful of your hand and deck size. Avoid getting screwed by Coldlight Oracle or by fatigue later on. A great combo I like to save for such matches is:
Emperor Thaurissan > Brann Bronzebeard > Gnomeferatu > Zola the Gorgon > Gnomeferatu > Gnomeferatu
A similar combo can be done with Dirty Rat to completely disrupt Combo decks.
vs. Aggro Decks
Mulligan hard for early removal and control tools. Defile, Demonwrath, Hellfire, Doomsayer, Deathlord and Reno Jackson are generally great options to have in your opening hand. Despicable Dreadlord can shut Paladins down pretty hard. Remember that Mal'Ganis grants you immunity, which is often life-saving. If you can make it to the late game, you have won.
It can be a very difficult match if they get an early Barnes. Sylvanas Windrunner was an addition to better deal with them (combo with Shadowflame for immediate results). Another fundamental tool for that match are the polymorph potions from Kazakus. If at all possible, pair him with Brann Bronzebeard. Trying to get Barnes out with Dirty Rat is very risky, so be careful in reading their mulligan. If I can stabilize, I like saving my Zola the Gorgon for N'Zoth, the Corruptor or for the Gnomeferatu combo and just running them out of cards.
Rise of Shadows: Fel Lord Betrug and Plot Twist synergize well with each other and with the deck. There are a lot of deathrattles, and they can add big minions to your N'Zoth, the Corruptor and/or Bloodreaver Gul'dan ressurect pools without you needing to play them. It can also be comboed for a possible board clear, and in desperation Plot Twist may be used for a shot at a better hand.