Hearthpwn

First of all, Paladin is the class which is the most difficult to budgetize. It has a lot of auto-include legendary cards like Tirion Fordring or Ragnaros, Lightlord. As new player it hurts to get a nice expensive card without the possibility to make a deck for it. I'm in the same situation except that I'm not new, I just have a smaller collection. That is the reason why I made this deck, and decided to post it to help others out.

As you can see I used the elemental package. Elementals are cheap and work quite well in Paladin with the possibility to discover Ragnaros, Lightlord from Servant of Kalimos multiple times. You can discover some good class taunts from Stonehill Defender too. Why Bonemare? Because it's the most OP thing you get for 40 dust. The end.

If you don't have Karazhan:

-1x The Curator +1x Grimestreet Protector

If you don't have Uther of the Ebon Blade but still want to play this deck:

-1x Uther of the Ebon Blade +1x Grimestreet Protector

 

Strategy:

Aggro

Taunting and board control is your win condition here. Most aggro decks need to be tired out in order to win against them, except for Murloc Paladin. You need to get out there stuff on the board until their hand is empty, then use Equality + Consecration to get rid of their murlocs. If you can't clear their board you have no chance to survive.

Tempo/Midrange

Three simple words: CLEAR THE BOARD. That's their weakness. After you clear their board there is no escape for them. Develop your own side and buff your minions in order to win.

Control

The control matchup is about value. The more Tirions you discover, the more you win /s. Rely on your buff cards such as Bonemare. Try to discover good things from Stonehill Defender and try to get Ragnaros, Lightlord from Servant of Kalimos to stay alive. Clear the board in the meantime. Uther of the Ebon Blade may help you reset your health and deal some face damage in the meantime. Control the board too. You will need to outvalue control in order to win. 

Jades 

Jade Druid is the archetype that I've been having the most problems with. However, with the help of some board control and taunts I could recover easily. Also I haven't tried, but Skulking Geist could help in this matchup.

Thank you for all the patience and upvotes! Hope you enjoy the deck!

Deck showcase by kiwiinbacon:

 https://www.youtube.com/watch?v=9ouKyb8aX50

Deck showcase by TheSynch:

https://youtu.be/9wXtKsryVNU

Update: http://www.hearthpwn.com/decks/931869-updated-budget-elemental-midrange-paladin