Hearthpwn

I tried for hours, using other decks here, to down Chromaggus. No luck. Then I decided to use my own deck, and this is the result. As a warning, I'll be the first one to say that this relies heavily on RNG. Don't have any 1 or 2 mana minions by turn 2? You're probably better off conceding and trying again. Anyways, onto the deck itself:

My deck takes advantage of the AI abuse that several other decks use. Specifically, when Kel'Thuzad and a minion with taunt are both on the field, neither the boss nor his minions will attack. Of course, it's totally possible for Chromaggus to use 2 Flamestrikes, 2 Swipes, or one of each to take out Kel'Thuzad, but this deck has some countermeasures to that. Here are the cards in the deck and their roles:

• The main star of the show is the Sorcerer's Apprentice. Lowering the mana cost of the cards Chromaggus gives you helps immensely, by allowing you to avoid its bad effects while at the same time using your own cards. While you could argue that Kel'Thuzad is more important, chances are you won't even be able to play Kel'Thuzad with a living taunt minion, since you'll have to deal with the (sometimes devastating) cards you're dealt by Chromaggus.
• Mogu'shan Warden and Arcane Nullifier X-21 are the cohorts of the AI abuse strategy. They can both survive one Flamestrike each, and Arcane Nullifier X-21 only ever takes 1 damage from Swipe.
• Taking advantage of the lowered spell cost, you've also got the Flamewaker and Mana Wyrm for extra damage, Mirror Image for protection and extra damage, and Gadgetzan Auctioneer for the draws (but if you get to the point where it's safe enough to lay down him, chances are you've already won).
• Sylvanas is great to trade with, preferably for a 9/9 or 8/8.
• Spellbender helps take the bulk of any Swipes Chromaggus throws at you, so your Mogu'shan Warden will survive. Mirror Entity is a great card to play after Chromaggus lays down his low attack minions, at around turn 5 or so. Duplicate helps early on in case you have a lone Apprentice and Chromaggus decides to use Claw or one of his minions to take her out. Kirin Tor Magi allow you to gain an edge by having a minion to trade with and a free secret, and Ethereal Arcanists are great to trade with. A 3/3 will take out the Chromatic Dragonkin while surviving, and a 5/5 will take out Technicians and most Azure Drakes while surviving.
• Emperor Thaurissan will allow you to play even more spells and minions, giving you an edge that grows every turn.
• Zombie Chow is great for taking out the Faerie Dragons that Chromaggus often plays on his first or second turns.
• Left over is one slot, which I decided to fill with Cairne Bloodhoof, but you can put anything there, really. Maybe a Blizzard or Flamestrike to help stall or kill the enemy minions.

Alrighty, now that we got that wall of text out of the way, here's what you want to mulligan. In descending order of importance: Sorcerer's Apprentice, Mirror Image, Zombie Chow, Mana Wyrm, and Kirin Tor Mage.

Now, more details about the Chromatic Affliction cards. Chromaggus gives you them in the following order: Green (restores 6 health to him at the start of your turn), Red (deals 3 damages to you at the start of your turn), Blue (reduces the cost of his spells by 3), Bronze (reduces the cost of his minions by 3), and Black (gives him an extra copy of each card he draws). After you get those first 5 cards, the rest are in random order. My opinion of the threat of these cards is Bronze>Blue>Red>Black>>Green. Depending on the status of the board, though, that may change. The lower your health, the higher the threat of red is. The more minions you have, the higher the threat Blue is. Green can pretty much be ignored until you have complete control of the board.

Here's a screenshot of my win:

As you can see, a combination of Thaurissan and two Sorcerer's Apprentices made me have a huge advantage. Hopefully, you have the same amount of luck I did!