I wanted to post the deck I've been using to reach 3 star masters. It doesn't have all the cards I'm hoping for, but it seems unreasonably powerful. It took around 20 games to reach 3 star masters, picking up a star every game.
The basic principle is that you want to trade 1 for 1 or better with every card your opponent plays until end game at which point all your cards are good and some of his are bad (because they're early drops). To that end, the deck plays very few cards that aren't either cheap removal or resilient creatures.
First, the deck:
2 Acidic Swamp Ooze
2 Faerie Dragon
2 Scarlet Crusader
2 Chillwind Yeti
2 Keeper of the Grove
2 Twilight Drake
2 Druid of the Claw
Why these cards?
The removal suite:
There are 15 removal spells in the deck. This is key to the philosophy of preventing any of your opponent's synergistic cards from working and also to not dying.
2 Claw, 2 Wrath, 2 Scarlet Crusader, 2 Faerie Dragons - these are your early game removal spells. If I could play 6 wraths and two claws, I would in a heartbeat, but I can't. Scarlet Crusader is pretty resilient and can usually trade 1 for 1 with a legitimate threat. Claw combines with the hero power to remove 3-toughness threats. And faerie dragon, while it gets AoE'd late, can often trade with something early.
2 Keeper of the Grove, 2 Bite, 2 Starfire - these are your mid-game 2-for-1's. Don't save them - just burn them as fast as you can get something reasonable. You have a lot more coming.
2 Swipe, 2 Starfall - These are fantastic cards. They kill swarms. They kill big things. I think Starfall may be the single best card in the game right now and it's certainly the best card in the deck.
1 Naturalize - Don't cast this. Ever. Except when you absolutely have to. Your fundamental strategy is to fight through every card your opponent plays and this hurts. But since this is the slowest deck in the format, you have to fight literally everything your opponent has. And that might include Ragnaros or Ysera. Naturalize is for them. I wish it weren't necessary, but it's an important hedge against things that could be devestating.
2 Acidic Swamp Ooze- Equipment is really, really, really good. There's one card in the game that destroys them. I guess that means we're playing it.
If we're going to play a creature, we want it to be resilient. Generally speaking, sweepers do about 2 damage (except flamestrike) and targeted removal or creature attacks do about 4. We'd like our creatures to dodge that. We can't dodge Shadow Word: Pain since the Keepers of the Grove are too valuable, but we can dodge Shadow Word: Death. So we'd like to have no minions with more than 4 attack if we can help it.
2 Chillwind Yeti, 2 Twilight Drake, 2 Druid of the Claw - These are the meat. They're sometimes 1-for-1, sometimes 2-for-1, and sometimes they win the game. The druid's of the claw are almost always 4/6 Taunts (because >4 toughness is important)
1 Cenarius, 1 Ysera - The Ysera is for the very, very late game. It's usually the last card you play once everything else is exhausted on both sides. She's been great. The Cenarius is pretty mediocre - something horrible usually happens to the treants and then he dies messily as well. If I had an Ancient of Lore, I'd play it over him, but I don't. It also dies to Shadow Word: Death, but the life gain and the cards are pretty nice
1 Nourish - This is another hedge. You need some way to keep yourself up on cards if something's started to go wrong. I think I'd play a second Ancient of Lore in this slot, since you never ever use the mana crystals and I often want some way to gain a little life
If I had the cards, I'd play -2 Faerie Dragon, -1 Nourish, -1 Cenarius and instead play +2 Ancient of Lore, +1 Bloodmage Thalnos, +1 Ragnaros. It shifts the deck slightly more top-heavy, but Thalnos is a fantastic card, and Ragnaros helps close out games quickly. It's possible that he's wrong since I haven't liked my other really expensive things and it should be something like a Healing Touch or something strange. I think I'd like to try out a King Mukla at some point in place of one of the early drops, but I'm not sure where yet and a Cairne Bloodhoof might be better than Ragnaros for that slot.
VS Mage: The controlling mage decks are easy. You have more removal and your creatures are designed to beat their removal. Be a little careful, count polymorphs before you stick Ysera, and keep your health above 15. Use Bite mostly as a healing spell and just work through their cards slowly. Don't let them keep spell power minions out and it should be easy.
Tempo mage decks are somewhat harder. Get rid of the Mana Wyrm and then they tend to play like controlling mage decks without the polymorphs.
VS Hunter: I've only ever seen rush hunter decks. They tend to play one spell a turn for a while and sometimes even 1 health things. Kill everything, then kill them. Don't rely on creatures since they tend to have removal and their creatures are often way bigger than they look since they have a bunch of buffs. If you can keep their creatures off the board, you'll win pretty handily.
VS Warlock: I've also only seen warlock rush decks. Same deal as with hunters, except their creatures tend to be even smaller and there are more of them. Your creatures are fantastic against their removal, so just keep your health up and you should be fine.
VS Warrior: Save your Oozes! Other than that, again, keep every creature off the board, prioritizing the Warsong Commanders. They have Charge creatures but very little removal, so you can lean somewhat on your druids of the claw. Try not to use bite and claw as removal if you can help it so you can stack your armor.
VS Paladin: There are two paladin decks that I've seen. The rush version tends to play like the hunter, but with less card advantage and way slower. Save your Keeper of the Grove for the silence in case something goes wrong and remember that they have basically no removal, so your druids of the claw can tank for you.
The controlling paladin deck plays the same game as you, but I haven't really seen any that go as all-in on the control. They have some dead cards (consecration, whatever they use early), but they're also one of the most likely decks to have huge legendary monsters. Save your naturalize and be ready with starfire. You can cast Ysera as soon as you have an opening and ride her to victory. Failing that, some mixture of the 4/5 brigade usually does the trick.
VS Priest: I've played against a lot of priests and haven't lost yet. The first trick is in deck construction: play 4 power creatures that you're not scared to face. The second trick is to count. They have 2 mind controls, 2 shadow word: pain, 2 holy nova. The mind controls are the ones you're worried about, but it's worth keeping the others in mind. Don't play twilight drakes with too much health (4/4 is about perfect or 4/5 if you have a starfire in hand) and be prepared to eat the 2-for-1 against the mind controls. Between the Nourish and the fact that they have dead cards, your late game is generally much better than theirs, so just be patient. Use the 2/3 drops to put pressure on them if the game stalls out - they have a tough time removing them other than the two Shadow Word: Pains
VS Rogue: I've played against 1 rogue. It was a kind of rush deck with lots of direct damage and not particularly scary. I imagine there's some brutal rogue deck out there, but I haven't played against it, so I can't really give advice.
VS Shaman: Kill everything they play. Try not to use spells to kill totems, instead use your creatures. They have some limited removal, but they tend to play lots of bad creatures, so swipe and starfall are your friends. This is one of the matchups where I most wish I had Bloodmage Thalnos.
VS Druid: DURIDS IS MUST ALWAYZ HALP EECH OTHER: sumtimes a new durid is need sum halp and advise frum a good durid so u shuld alway halp unother
There are 9 rares. You need them. So that's 900 dust or a little luck. The two legendaries are not at all necessary. Ysera is very nice, but you'll be fine with another 4/5ish creature in their place. Try Azure Drakes (which I don't have, so haven't tried) , Gadgetzan Auctioneer, or Argent Commanders.
The druid special mechanic is cards that have a choice. This is awesome! Most of them have a normal mode and then an unusual mode, but that versatility is great.
Claw/Bite: Normally these are removal spells. Against rush decks or mages, though, think of them more as armor spells - try to attack the enemy hero rather than minions to better preserve your life total
Wrath: This is almost always a 3 damage spell. Only play the 1 damage side if you're desperately looking for a particular card or you can't attack with your hero for some reason.
Keeper of the Grove: Both sides are nice. I generally use the 2 damage side, but it should be clear which is best. The choice aspect on this card is very strange sometimes - it works on Faerie Dragons, but the Spellbender mage secret will redirect it. There's probably some bug at work here, but I'm not sure exactly what's intended, so be a little careful.
Starfall: This is your best spell. Both modes are awesome. You have a ton of removal, so don't hesitate to use this to kill 2 2-health minions or just to take down a yeti
Nourish: I've never used the mana crystals. I can't imagine using the mana crystals. Do you really want to play Ysera that early? She'll just get polymorphed, assassinated, or, even worse, mind controlled. Just draw the cards
Cenarius: Should be obvious - use the +2/+2 if it wins you the game and generally make the treants otherwise
The main takeaway from this is that in building a control deck, your main job is to invalidate some of your opponents cards (as many as you can). Pick your creatures and your spells to be as versatile as possible and as resilient to the commonly played cards as possible. This is why we don't play Innervate, Wild Growth, Moonfire, or lots of the other popular cards: they're often not worth a full card. We want every card in our deck to be useful and our hope is to strand the opponent with cards that don't do anything in their hand.