Edit#1: These decks are legendary-less as well... they are basically rare-s and below only decks.
Edit#2: Check out The Case for Budget Decks: Zoo & Things thread at Hearthstone Reddit for more budget decks.
If you are a budget player or just starting out in Hearthstone and are looking to build a competitive or some-what competitive deck, Hearthstone Topdeck website is a website with excellent resource for that with decks from competition as well as their dust cost shown. Cheaper decks have their dust cost highlighted in green and from the many that I'm looking at, their highest rarity cards are rare-s.
After searching around for a while, here are the top 3 "Epic-less" decks, ordered in terms of least number of rare-s, I can find at this point of writing:
#1 - Trump's Naxx Backspace Rouge (Aggro Rogue)
This deck was piloted by Trump at a recent DKMR Invitational tournament and only features 5 rare cards in total, not counting the Naxx Nerubian Egg! Trump also calls it the Free2Play Rouge and you can view his plays from his Twitch account's past broadcasts, where I think it shows him building up the deck from scratch. It is basically an Aggro Rogue deck combined with some cards from Zoo Warlock. I was curious about the name, Backspace, so I searched and found out it originated from a player named, Backspace. His version has more rare-s and epics (no Naxx cards as it was written before the Naxx came out) so it is something to improve upon to make the deck potentially stronger in the future. The neutral cards used are also commonly used so they can help build other decks as well. Out of the other Naxx cards, I think Spectral Knights might be able to replace Azure Drakes bringing the number of rare-s required down to 3!
Update#1: More "Epic-less" Aggro Rogues deck list: 1 and 2.
Important Rare-s common among the Aggro Rogue decks: SI:7 Agent, Azure Drake, Blade Flurry, Perdition's Blade
Update#2: Trump retires F2P (Free to play) Rogue deck at Rank 3. Makes Zoo instead. I've read through the comments and there was one saying the deck was similar to Zoo and I thought the initial decklist had a lot of commonly-used Zoo cards. (Trump's last version of the F2P Rogue had even more cards of Zoo Warlock than the initial decklist) There was also post stating how hard it was to rank up at rank 5. I guess if you are still building this deck, go for the original Backspace Rogue variant with Trump's F2P Rogue as base first.
#1 - Midrange Hunter (Note: Blizzard's balance changes affects a key Hunter card from 22 September 2014 onwards)
There's an example decklist in this article at GosuGamers.net that showcases one with Nexxramas (Naxx) first wing cards. The reason why I tied this deck at number 1 is because of the possibility of using an early version of it with just one pair of rare-s first: Savannah Highmane, according to Pocket Gamer as the others can be replaced until you get them. The only cons about that the deck I can think of is that their neutral cards are not so easily transferred to other decks as it is kind of beast-themed. The last time I checked the Hearthstone Topdeck website, there were hardly any of them in the tournaments but I think it gets a good character class card in Nexxrammas, Webspinner, which will probably go straight into the decklist.
Update#1: Here are a couple of Hunter decks from Limited formats without Epic cards: 1 and 2. The links point to the tournament so you can view other Epic-less decks there. Browsing through the top few Hunter decks, Flare has been found in practically everyone of them.
Update#2: More decklists:
- Reynad's Midrange Naxx Control Hunter from 2p.com (with mulligan tips)
- Naxafari Midrange Hunter from 2p.com (includes deck tech video)
Important Rare-s common among the decks: Savannah Highmane, Eaglehorn Bow and Flare.
#3 - Naxx Zoo Warlock (or Zoo-lock as it is commonly known as)
This is a very popular deck and I've read that it is usually the easiest competitive deck to build. However, it wasn't so when I compared the number of rare-s it had to the other two decks above. Trump has again a version with the least rare-s; 6 not counting Nerubian Eggs. With that said, it is still a very strong deck, especially with Naxx cards addition, and unlike Trump's Naxx Backspace Rogue, it is basically the "final form" of the deck. Thus, even though it requires more rare, it is potentially the strongest of the 3 listed here. It also has neutral cards which can be shared with other decks like Naxx Backspace Rogue too.
Update#1: More "Epic-less" Zoos: 1 and 2.
Update#2: WEC World Cup EU Zoo deck with Naxxs cards.
Important Rare-s common among the decks: Doomguard, Young Priestess, Knife Juggler and Defender of Argus. (Trump's version seemingly replaces Young Priestess with Nerubian Egg)
----
In summary, Naxx Zoo Warlock is still probably the best deck to go for in the beginning even though it costs more. If you want a deck as soon as possible, go for Midrange Hunter with a pair of Savannah Highmane first. Trump's version of Aggro Rogue is also not too expensive to build while being able to transit into the more expensive version in the future as you get more cards.
I think all 3 decks are good and probably should be the first 3 decks one should build unless you don't like any of those 3 classes. Whatever you choose, it is best to concentrate on finishing it rather than spreading the cards around.