Hearthpwn

I used this deck twice now to defeat Galakrond via fatigue - unlike almost all other decks posted here that use an OTK combo (or a 2 turn combo via freeze mage. I don't find OTKs satisfying and hence I came up with this deck

Assuming the replay stays available for all eternity, here is the deck in action: http://replays.firestoneapp.com/?reviewId=b3c08056-9ed5-43de-a604-1e022dc8068a&turn=8&action=3
And while I admit that I had a very lucky start there, I promise that not much luck is needed with this deck. If you have a mass hysteria and another AOE or a shadow vision, and Galakrond does not drop 8/8 minions on his first turn, then things look already pretty good.

In addition to not being an OTK, the deck is rather cheap, as no epic nor legendary is vital for succeeding.

Absolute must haves: Mass Hysteria, Grave Rune and Khartut Defender. In addition you need at least either Convincing Infiltrator or Sylvanas Windrunner. Without Mass Hysteria your chances are almost zero. Missing the other cards will drop your chances notably, though it is probably still doable.

High impact cards, but not must-haves: Shadow Visions, Twilight's Call, Lightbomb, Sylvanas Windrunner, Lesser Diamond Spellstone, Soul Mirror, Plague of Death, N'Zoth, the Corruptor.

 The idea of the deck is to use Mass Hysteria, Lightbomb, Plague of Death and Soul Mirror to clear his massive boards. Again and again and again.
All other cards support you in keeping you alive. The overall plan is to fatigue Galakrond. Since Galakrond does draw *at least* 6 cards more than you do (usually 9+), he's going to be far ahead in fatigue. Assuming you start with 30 HP into fatigue you can go for at least 9 rounds without dying. Galakrond can survive at most 17 rounds. The deck contains no minion duplicates, such that Galakrond does not reduce the card difference. If it would contain duplicates then these should be Khartut Defender or Convincing Infiltrator.

Now the details:
Galakrond goes tall *and* wide, by invoking 8/8 dragons and playing things like Scion of Ruin and Dragon's Pack. Mass Hysteria can deal with almost any board, which is awesome. Lightbomb [/card]cannot kill some of his minions, so it's not as good, but it's mostly his 4/5 minions (from [card]Dragon's Pack and Shield of Galakrond) that you have to worry about when using this spell.
Soul Mirror is ideally used when he has Waxadred out, granting you a copy of it in your DR death pool. A big downside of Soul Mirror is that it likely puts undesired small minions into your death pool. So it's definitely not a must-have card. (Note that it's highly advisable to have *some* card that can deal with his Waxadred permanently, but this deck already has multiple options to do so)
When playing, be aware that Galakrond can deal at most 8 damage from hand to face using two Nether Breaths. Furthermore, Fiendish Rites allow him to buff all his minions, so ideally also count for that card, as it's almost the same as face damage from hand. The last card that can allow him to get unexpected damage on you is Praise Galakrond!, but that's just one damage, so you probably don't have to be careful with that card. Hence track what he played already and prepare for the worst. 
However, even if the number of enemy minions seem overwhelming, if he cannot get lethal and you can play one of your impact DR minions (Convincing Infiltrator, Khartut Defender, Tunnel Blaster and Sylvanas Windrunner), then it might be a good idea to do so, just to have them in your death pool.  You can later resurrect the minion with one of your cheaper resurrection spells (Resurrect, Eternal Servitude, Twilight's Call) and then put a Grave Rune on it. This is particularly powerful on Khartut Defenders as you will get a total of 6 death triggers (18 life) and lots of damage to enemy minions as they run against your taunt wall.

One note on gameplay and AI:
The AI in the game does *not* understand death rattles. The AI understands almost nothing that's written on cards. Imagine that it only sees a Khartut Defender as a 3/4 minion with *some* DR and *some* other ability named Reborn (I doubt the AI knows the actual meaning of reborn). It also sees that the card is worth 6, so it's a strong minion. But it does *not* understand the text. For that reason, it is often scared to trigger DRs. That can be used to your advantage.

Notes on specific cards:
Plated Beetle: this is not a core card, but you probably want something besides Khartut Defender to give you some healing. Rotten Applebaum is another good option, but it costs notably more (the taunt does help in case Galakrond cannot use his hero power on this minion, though, so consider trying Applebaum).
Resurrect: This is a great card to play in combination with Grave Rune. It's not a must-have, though, as the lack of choice makes this card a lot weaker than Eternal Servitude.
Eternal Servitude: Ideally targets an impact DR minion. Very useful card in this deck.
Twilight's Call: ideally revives two different DR minions. This is also one of the best cards to be used in conjunction with Archmage Vargoth. Galakrond does even rather target Vargoth with his hero power than duplicate 1/1 DR minions, which is to our advantage.
Lesser Diamond Spellstone: Ideally only play them when fully upgraded, but as long as you can resurrect at least 2 minions this card usually already pays off. If you can resurrect Vargoth, you might have already won.
Shadow Word Death: This is solely to deal with some very early 8/8 minions or in case after a Mass Hysteria an 8/8 stays alive. Due to the high amount of efficient mass removal, this is not a must-have card in the deck.
Deathlord: Now we get to some tricky stuff. This card should *never* be played early, as it will give your opponent tempo for free. But it is also a great target for Grave Rune, as it will a) bring Galakrond closer to fatigue and b) it usually pulls some invoke-Battlecry minion, thus reducing the amount of board flooding your opponent can do. Due to the trickiness of this card, it's quite a flex card and can be replaced by some other safety mechanism. Use it only if you see yourself capable of making the right decision on when to use this card. Used wisely it saves you some hit points and it can be responsible for 50-100 fatigue damage. To see what I mean maybe checkout my replay above - I used Deathlord [/card]only when I knew I could deal with whatever Galakrond gets from it)
[card]Archmage Vargoth: This is not a must-have card for the deck. But it grants a lot of flexibility to many of your spells. And if it is in the death pool and gets resurrected by Diamond Spellstone - great value gain there.
Excavated Evil: This is not a must-have, but it's the strongest damage-based (spell) board clear against a flood of small minions that priest has. It can be semi-replaced by other board clears that deal 2 damage (like Holy Nova). It's just yet another AOE. Since we mostly want to get rid of Scion of Ruin with this card, 2 damage would be enough. 3 Damage, however, also kills Umbral Skulker, Nithogg [/card] eggs, and the rarely seen unbuffed Spirit Wolves.
[card]Entomb: There is no need to have this card, but it can deal with 2 serious threats that your mass removals cannot: Waxadred and Zzeraku the Warped. Try not to use this card on other minions, if you can.
Tunnel Blaster: This card is expensive, but the effect is pretty great. It can be replaced, but it allows for board clears off of your resurrection spells and Grave Runes. And the AI really does not understand the DR as proven in my replay above, when it uses an 8/5 dragon to kill the blaster instead of its small minions.
Plague of Death: This is yet another AOE. Two of these are probably good if you have them. This is another way of dealing with Waxadred [/card]and [card]Zzeraku the Warped. While your own minions' DRs will not trigger, the minions themselves are still ending up in your death pool, so don't be afraid to kill your own guys.
N'Zoth, the Corruptor: With so many DR minions this card is a must. It is not decisive for winning, but it buys you *at least* one turn, often even up to 2.5 turns.