There are a lot of decks that have been around since Beta. Here are a few decks that have been around since the beginning:
Handlock - Tap into cards and play Giants out in the mid-game.
Control Warrior - Use weapons and cheap removal to survive until the late game, where you unleash a powerful legendary every turn.
Freeze Mage - Even with all the freeze spells getting mana increases, this deck has never truly gone away.
Shockadin - Lots of divine shield and cheap minions. Flood the board, make value trades. This is pretty much the same as the new Aggro Pally.
What's important is that Blizzard has continued to release cards that enable new decks.
Zoolock(Naxx) - Zoo already existed as an OK deck, but Naxx reshaped it into something new. Eggs and Deathrattle minions allowed for old buffs to get extra value and the deck grew to dominate the board instead of rushing face.
Mech mage (GvG) - Used mages existing removal spells and the new mech synergies to create an a fast paced aggro deck, that had lots of reach for lethal.
Patron Warrior (BRD) - A single card and a bug fix turned a bad combo warrior deck into a very dominating Deck that is everyones favorite deck to hate. One turn kills and crazy amounts of draw, patrons getting in here, and berserkers hittings faces.
You'll continue to see all of the old decks grow and change with each expansion as well. The current Shockadin is a really good example. Here is one of the original decks:
If you compare it to the newer ones you can see how it changed.
Worgen Infiltrator was replaced by Southsea Deckhand once Paladins had more access to weapons.
Argent Commander was removed because 4 damage wasn't enough for the high cost, replaced by a better finisher like Leeroy or Arcane Golem.
Bluegill Warrior was replaced by the Shielded Minibot, a purely better minion for sure.
Avenging Wrath & Hammer of Wrath were replaced by faster more efficient spells like Muster for Battle & Blessing of Kings.
Edit:
This was in response to WesternHeretic about old decks. I just got distracted while writing it