Really, in the current meta, weenie decks can do no wrong. Packing your deck with the under-costed neutrals like Fairy Dragon, Harvest Golem, Cleric, Dark Iron Dwarf, and Azure Drake almost feels like cheating. I've just been doing that and supplementing with class based removal and have been rolling over people in constructed. The only real danger is over-extending into aoe board clears like Flamestrike, Hellfire, Swipe, etc. But if you just keep that in mind and don't over-commit, then you're pretty much guaranteed a win. The only time a weenie deck will lose is if your opponent got there first (i.e. he's also playing a weenie deck, but just got a better hand). Usually, it means he got the coin and was able to get his 2-mana minion out before me.
The optimist in me believes that there's other strategies that work, but now that I've been playing the game for a month, the limitations in the small card pool are starting to show. I've tried decks that rely on combos, but the chances of you getting said combo in hand is pretty slim. Unleash hunters get around this using the buzzard for card draw, but I have yet to lose against an unleash hunter while playing a weenie deck. Unleash hunters need buzzards + beasts to work, and if they have those in hand, then they probably don't have enough removal in hand to keep up with removal against all the minions coming out.
I think one of the strongest decks against a general weenie deck is a paladin playing weenie deck. Equality is pretty absurd and if you couple it with Consecrate it's even better. Also, Equality + Avenging Wrath is pretty fantastic as well. Throw in some bubbles in there and you can get better trades in the early game against a Rogue or Warrior playing weenies.
Inevitably, Blizzard is going to add more variety with expansions, but that's at least a year away, if not two years given the pace that they develop and the fact that this game isn't even in open beta yet. One thing that would help would be to add more lower cost neutral epic/legendaries that do weird/interesting things. Doomsayer is kind of in the right vein, but is easy enough to handle.