So, i bought some card packs today, and after opening them i had a golden Tirion.
Guess what? i made a paladin deck. The sdame card pack opening yielded me a captain Greenskin, and i wanted to use them both in the same deck. The deck is currently doing fine, i'm steadily climbing, around rank 14 now but games take quite long so it takes a while. I'm writing this because i think it could definitely be improved, and i'm by no means an experienced paladin player.
Here's my list:

2x southsea deckhand
2x Equality
2x Bloodsail Raider
1x Ironbeak Owl
2x Sunfury Protector
2x Wild Pyromancer
1x Sword of Justice
2x Acolyte of Pain
2x Aldor Peacekeeper
1x Big Game Hunter
1x Consecration
2x Truesilver Champion
1x Sen'Jin Shieldmasta
1x Defender of Argus
1x Azure Drake
1x Captain Greenskin
1x Stampeding Kodo
1x Avenging Wrath
2x Argent Commander
1x Guardian of Kings
1x Tirion Fordring

The idea behind the deck is to abuse the paladins weapons with bloodsail raiders and greenskin and the deckhands while keeping board control using the other, more common, paladin cards in the deck. The win condition is usually a 6/4 ashbringer.

Card draw is a bit of an issue right now, so i may craft LoH for that.
Match up wise i've only lost to a control warrior (he facelessed and then dreamed my Guardian Of kings and proceeded to Rag me to death), and a ramp druid, where i didn't draw into my removal when i needed it. It does quite decently against aggro, although i havent played against it much yet. I beat handlock, priest, and other paladin control, and haven't played against a miracle yet.

Please tell me what you think, any advice i swelcome, but bear in mind i may not have every card, so that could be the reason things like Rag aren't in here.