Hearthpwn

This is the deck I used to beat Chromaggus on Heroic Mode. I was struggling greatly with this boss, but I beat him first try after making this deck.

Update History:

Swapped Northshire Cleric for Zombie Chow--it was difficult to get draws off of it, and Zombie Chow would trade 1-for-1 with the Faerie Dragon Chromaggus often plays early.

Swapped Mass Dispel for Antique Healbot--Mass Dispel proved too slow, and some people reported they were having trouble staying alive before they could get out Kel'Thuzad and a Taunt.

Swapped Temple Enforcer for Auchenai Soulpriest--some people have mentioned Temple Enforcer as also being too slow, and the standard Auchenai Soulpriest + Circle of Healing combo can help keep you alive early. Also, Brood Affliction: Green.

Swapped Auchenai Soulpriest for another Antique Healbot and one Shadow Word: Death--while Auchenai Soulpriest does synergize very well with Circle of Healing and Brood Affliction: Green, it clashes with Lightwell, one of the focal points of the deck. As such, I have switched it for another Antique Healbot for more sustainability and a Shadow Word: Death to deal with Drakonid Crushers, Alexstrasza, Onyxia, or the horribly dreaded Nozdormu. By all means, if you want to go YOLO mode, feel free to put the Auchenai Soulpriests back in.

Some people are suggesting Mountain Giant in place of Mogu'shan Warden--I've done some testing on this, and I feel like Mountain Giant is far too slow. You will have to pay Mana for a creature that doesn't have Taunt or a healing effect, and it will have to pick off enemy minions one by one. The Mana would more rather be used on a Brood Affliction, I feel, and the Taunt on Mogu'shan Warden doubles your chances of having a Taunt available when you get out Kel'Thuzad. If you're having trouble, feel free to try this change to see if it works for you.

Guide:

There is a bug with the AI where if you have Kel'Thuzad and a Taunt on the field, the opponent's minions will not attack. Many people, myself included, have used this to beat previous bosses of Blackrock Mountain on Heroic Mode.

You have three win conditions: getting Kel'Thuzad out behind a Taunt, buffing up a minion enough to kill Chromaggus in a few hits, or buffing a Lightwarden from Light of the Naaru to the point of insanity (see the second picture at the end of this section). Your goal is to stall out the game long enough in order to achieve one of these win conditions and beat Chromaggus. Lightwell is the core card in helping you survive the early game. 

Mulligan for Zombie Chow, Lightwell, and Dark Cultist. Shadow Word: Pain and Silence are also good to keep to shut down the Chromatic Dragonkin. You can keep a Deathlord or a Mogu'shan Warden if you already have a buff spell in your hand, but it makes your early game a bit riskier.

The other cards are mostly spells dedicated to buffing up a big Deathlord or Mogu'shan Warden to stay alive. Once you have Kel'Thuzad, play him behind a buffed-up Taunt, and it's a free win from there.

Brood Affliction: Green is perfectly fine to keep in your hand, and Brood Affliction: Red is generally okay to hold for a few turns as you have enough healing with your Hero Power and Lightwell to survive long enough anyways. However, Brood Affliction: Blue and Brood Affliction: Bronze are necessary to get out as soon as possible. Brood Affliction: Black is not a huge threat as long as you instantly play Blue and Bronze, and Red will become a bigger threat than Black as the game goes on. However, the one problem with keeping Black is that if Chromaggus draws Swipe, he can double Swipe your Kel'Thuzad. If you stabilize early with a decently high life total, you can temporarily keep Red a bit longer to discard Black as soon as possible. In other words:

Bronze > Blue > Red/Black > Green

Until you stabilize with a buffed minion and/or Kel'Thuzad, prioritize trading with Chromaggus's threats over face damage. Especially if your minions have 4 or less health, such as Lightwardens, Chromaggus can clear them with Swipe or Flamestrike and pressure your health total.

Use Circle of Healing to cheaply heal your buffed Taunt minions and/or Kel'Thuzad, even if it heals Chromaggus's minions as well. Kel'Thuzad is still prone to damage from Swipe and Flamestrike, so if he's at 4 health or less, heal him up immediately. Buffing him certainly isn't a bad thing either.

Don't be overly greedy with your buff spells! Don't try to wait until you can heal that 2/13 Deathlord back to 16 health before you use Divine Spirit, nor try to wait to draw Divine Spirit before you use your Inner Fire. As long as a buffed Taunt can handle the board, then it's fine to buff it. You have to work very quickly in order to survive.

Almost always, you want to use Light of the Naaru on your Hero. However, if you already have a buffed Taunt up, you can use it on that to keep it alive for longer.

If you see him play Nozdormu, you'd better be prepared to kill that thing in a matter of seconds. Blizzard said they fixed this glitch with a previous boss, but it seems to resurface here. Nozdormu might not even give you two seconds to make a move.

This strategy is quite reliant on your draw RNG, but it certainly works if you have a little bit of luck. If you can't win, don't give up!

If you get good draws and play it right...

This can happen.

Videos of Gameplay:

Note: The decklist may differ in the videos as I update it very frequently. Regardless, any version of the decklist should mostly work in the same way given varying amounts of luck.

Credit to Kizaru1 for this video:

Credit to Windslot for this video:

Credit to Matt_Sparks for this video:

If you managed to beat Heroic Chromaggus with this deck, then give it an upvote and comment! If you managed to beat it with an altered decklist, post your changes here, and I may consider them. If you are unable to beat him using this deck, then perhaps give a suggestion to improve the deck or post why you are having trouble. Remember, this is really about luck of the draw. It takes people anywhere from one try to thirty tries. Don't give up!