I probably played for at least a year now and did manage to amass quite a number of cards from occasional playing to earn coins for packs. I also got lucky and had about 5-6 legendaries opened from pack so far but most of them were used in competitive decks anymore or only appeared in a deck list once in a blue moon. Thus, I dusted most of them for useful epics instead. Most of the "budget" decks from the past, like old school Zoo, are no longer viable and you'll probably need some epics for each class now in deck building as the game has already progressed quite a bit.
I enjoy playing a variety of decks and was able to build a competitive deck each for all the classes with the cards I have, using only legendaries from Adventure Modes. Here are the decks I am able to netdeck:
Hunter
JAB's Midrange Hunter (I replaced Dr. Boom with another Piloted Shredder. JAB suggested Sludge Belcher)
Hunter was more or less the only budget deck that "survived" through all the expansions. It does well without any epics (Snake Trap used to be in the list but nowadays it's optional) and legendaries (Dr. Boom is nice but not critical to the deck).
The other usual deck options are Face Hunter and Hybrid Hunter which are also relatively cheap to build although I'm not a fan of the play-style. Check out HearthstoneTopDecks.com for a list of hunter decks.
Update: I've tried out Brian Kibler's hybrid Hunter and am liking it so far. Decklist at his Archon League post and the deck does not need any replacement for legendaries as it uses none.
Warrior
Lifecoach's Patron Warrior
Warrior used to be a class that mainly only had one competitive deck, Control Warrior, which was very expensive with many legendaries. Blackrock Mountain introduced Grim Patron giving Warrior a new combo deck and also a relatively cheap top tier competitive deck IMO. You sometimes find competitive decks running Grommash but it isn't a necessary card.
Some other budget options include Kolento's OTK Warrior and MrYagut's Face Warrior.
Warlock
Rdu's Combo Warlock (I didn't craft the second Big Game Hunter and Ironbeak Owl but replaced them with Imp Gang Bosses)
After the nerf to Undertaker and Soulfire, Zoo was hardly seen in the competitive scene. I think it is still playable (MrYagut has an old-school zoo deck list with Blingtron that I will just replace with Loatheb) Xixo also made a version with Sea Giants when GvG came out and gave Warlock Implosion. The latest version you see nowadays of Zoo is now Midrange Demon Zoo with a number of legendaries.
One of the other recent popular Warlock decks Malygos Warlock, created by MrYagut. Unlike other legendaries in most decks, Malygos is the core card for that deck and the main win condition so you need to have it in order to make the deck work. (The deck is named after the legendary after all) The last variation of Warlock decks is Handlock which has been around for quite a while and it is too expensive with the double epic Giants.
Combo Warlock is quite an interesting deck and people normally don't expect the deck to combo lethal with the Arcane Golem+Power Overwhelming+Faceless Manipulator.
Update: Silentstorm's Warlock Zoo uses 0 legendaries and also 2 copies of Bane of Doom instead of using the usual 1 Bane of Doom and 1 Malganis. It is pretty much an old school zoo deck.
Rogue
Dog's Oil Rogue (I replaced Bloodmage Thalnos with Kobold Geomancer because the spell power is the important component of Bloodmage Thalnos IMO)
After the nerf to Gadgetzan Auctioneer and Leeroy Jenkins, Miracle Rogue still stayed around for a while and people were also still playing the Auctioneer. Once Tinker's Sharpsword Oil came along in the GvG expansion, Oil Rogue became the main competitive Rogue deck and with 2 epic Preparation cards, it isn't too expensive either.
---
The following classes are IMO not as viable as the ones I listed above, due to either being perhaps not as strong or requires more expensive cards in order to be better.
Shaman
WingsOfWax's Budget Mech Shaman
I wasn't doing too well with StrifeCro's Overload Shaman and find WingsOfWax's Mech Shaman deck a little better.
Update: Finally found a Mech Shaman list without Fel Reavers: Tempostorm's Korean Mech Shaman. It does require 2 Doomhammers and a Leeroy Jenkins though. I only have 1 Doomhammer but replaced the other with Earthshock and the Leeroy with Hex. I think I could change 1 of them for Lightning storm as it is a good board clear for when you get behind on board.
Priest
Lifecoarch's Deathlord Priest (I might consider replacing a Holy Nova with Mind Control as Holy Nova does not clear Grim Patrons)
I think Priest is not in a strong spot now, even though the class is one of the cheaper control decks to build.
Mage
Lifecoach's Mech Mage (I replaced both legendaries with 2 Arcane Intellect)
I remember Mech Mage first being used by StrifeCro in a tournament finals and it was basically the new "Zoo" deck for a while. However, the main problem is the lack of card draw other than Arcane Intellect whereas Warlocks have the hero power to refill the hand. Once you lose your board as a Mech Mage, it is usually over.
Paladin
Rdu's Aggro Paladin
I'm not a fan of "face" decks but this is the cheapest competitive Paladin deck at the moment that I have not tried yet. Midrange Paladin contains quite a few legendaries so it is out of the question. One of the legendary that is in almost all Midrange Paladin is Tirion Fordring and he seems too powerful to ever be replaced.
Update: I prefer this Aggro Paladin decklist from Tempostorm over Rdu's version. I replaced the Leeroy Jenkins with Equality and Equality is just such a powerful card that can be used to retake the board should you lose it.
Druid
MrYagut's Aggro Druid (I would replace Blingtron with another Defender of Argus)
The issue with Druid is that he needs at least 4 epics in Force of Nature and Ancient of Lore while most other classes only needed 2 epics the most. MrYagut's Aggro Druid is the cheapest Druid deck that I could find and I am still miss crafting some of the rare cards in order to test this.
Edit: I will most probably not complete the above deck because I find Coldlight Oracles to be a waste of dust as it is mostly used in mill decks which I have no intention of building even though it may be a fun deck to play. The cheapest Midrange Druid that I can find is Zalae's and I rather work towards that replacing Harrison Jones with Acidic Swamp Ooze or another Sludge Belcher and Dr. Boom with Sunwalker.
The decks I listed above are pretty decent enough for me to play quests and also climb from rank 25 to around rank 10. I've stopped buying packs for the moment and am currently saving up gold in case there is a new expansion set announced on the July 22 live stream event by Blizzard.
