Hearthpwn

This is the deck I used to kill Heroic Baron Geddon with. The most important thing is to use up all of your mana every turn, so this deck is designed to help you do that. First, you want to use your hero power a lot to conserve cards. The fewer cards you play, the more mana you can use during the game. This deck is about outlasting him. The Clockwork Gnomes and Webspinners will help you out with their deathrattles. Save your Brewmasters to cast on big minions he used Living Bomb on. You especially want this for Kel'Thuzad. Once it gets to the late game, if you have several Brewmasters left and KT, you are in very good shape. Always keep in mind he will cast Living Bomb on your best minion. You want to make sure you have a way to kill the minion he casts it on if you can't bounce it back to your hand. Arcane and Quick Shot are useful for this purpose. You probably want to save them to use on your own minions, cuz you can't afford to take that 10 damage. 

Once I added the brewmasters, it only took me a couple of tries to win. Bouncing a few Living Bombs back to your hand really takes the wind out of Geddon's sails, especially if you get some KT revives, especially if you revived Sylvanas. 

You absolutely must have a 1 cost card in your hand on turn 1. Just concede and try again if you don't. Do not add any more low-cost cards to this deck. You need to have enough expensive cards to be able to use your mana up every turn for like 15+ turns (I really should have made a note of how many turns to beat him, but he was almost running out of cards with about ~4 cards draws).  Also, keep in mind you'll only have 8 health if Executus dies. If you time his death right, your hero power will give you some good burst to finish the game, but he's also probably gonna throw down his two molten giants near the end, so you need to be able to deal with them.

Subs:

Coldlight Oracle - The card draw is the important thing here. Also, the 3-mana cost is important so you can spend mana on odd turns. You could try replacing it with something similar, like Acolyte of Pain, or you could go for Loot Hoarder or Gnomish Inventor, but you should switch out another even-cost card for an odd-cost, probably

Arcane Nullifier X-21 - This card isn't that important to have. I put it in to help protect your board, and also because it can't be targeted by his control cards. You could put it a Shieldmasta instead for the taunt, or you could put in a Faerie Dragon that is immune to Living Bomb. Might be good in the early game. Or you could try a Piloted Shredder to get some use out of its Deathrattle. It would be a good sink for a Living Bomb.

Gladiator's Longbow - The 7-cost is what is important. Throw something else in that costs either 7 or 9. You could try Dr. Boom, Stormwind Champion, or Ravenholdt Assassin. The stealth on the latter might come in handy to avoid Living Bombs.

Sylvanas Windrunner - This card is pretty important to the deck. Stealing some of his cards gives you the damage to finish him off. You could try replacing it with a Sunwalker. Whatever you do, do NOT put in Thaurissan. You do not want to lower the mana costs of your cards or his hero power will kill you.