Hearthpwn

"Drink with me"

Thats a sentence you'll hear often in Arena but almost never in ranked play. It is what Youthful Brewmaster says when hes summoned on the board. I think the card is undervalued at the moment. It can be very versatile in combination with battlecry creatures, the most powerful of which are present in the Paladin Arsenal. I'll explain my deck by going through my choice of battlecrys. Then I'll explain the interaction of those cards with brewmaster.

Battlecrys:

2x Ironbeak Owl: In a meta full of deathrattles having a silence is key. I prefer the Owl over spellbreaker as it's cheaper and most of all it is a good response to aggressive decks. Having an Owl can disrupt the explosion of Hunter and Zoo decks. I'd argue that playing an Owl on turn 1/2 in response to an undertaker is one of the best openers you can have as a control deck.

1x Earthen Ring Farseer: Earthen Ring is a tech against Aggro decks such as Zoo and Hunter. It increases the time you survive against them. It can become a prime target for the hunter player as he might not want Earthen Ring to run in a freezing trap. It is versatile as it can heal your own minions.

2x Defender of Argus: Defender is an excellent card in almost any deck with cheap creatures but it really shines in Paladin. Being able to produce a 1/1 "dude" as hero power guarantees that Defender will always get some value. Usually it will even get full value by taunting up 2 creatures. The card is a defense against aggro decks as well as a threat of its own in control matchups. Having like a 3/2, a 2/3 and a 2/2 might already force board clear in control matchups.

2x Elven Archer: This may sound like a really odd choice. The Elven Archer replace the role that is usually played by Wild Pyromancer in Control Paladin. Compared to Pyro the Archer has some advantages. It is very good early in the game against aggro decks that nowadays often play cards like Leper Gnome or Loot Hoarder. On its own it also gives the one critical damage to make a trade favorable later in the game or kills e.g. the leftover of Auchenai Soulpriest after a Circle of Healing. Played together with Equality it has the disadvantage to only kill one enemy minion in comparison to Wild Pyromancer killing all. This is only a minor problem in control matchups such as warrior where there is only one major threat usually. And against aggro the early game potential should make up for this. It might be problematic against Shaman. An advantage is that an Archer doesnt necessarily kill what is on your side of the board  as Pyro does. A beautiful thing is the interaction Elven Archer has with Brewmaster possibly dealing 2 damage early in the game or killing multiple big threads after an Equality.

2x Gnomish Inventor: Together with Lay on Hands these are the decks sources of card draw. The Inventor makes a last resort target for Brewmaster in order to be cycled but usually it performs well enough on its own as a body to be buffed by Defender of Argus or as killer of small minions. I prefer Gnomish over the drake as the even higher 5 mana cost would impede interaction with Brewmaster a lot more. Also this deck already runs a lot of 5 drops and only 2 spells that would profit from spellpower.

1x Stampeding Kodo: It's great with Aldor Peacekeeper, against warrior and against Aggro. I play only one though as it doesnt always have a useful target and there are other cards that are more important.

1x Alexstrasza: Yes this is a battlecry too ;) It helps you survive if aggro decks had a strong opening and in control matchups it introduces the swing moment where you change from the defending plan to the offensive. 

1x Harrison Jones: An important card in the current meta where Hunter and Warrior are played often. It makes the matchup against miracle favorable

Cards that dont need much explanation probably: 1x The Black Knight: Taunt Removal.1x Guardian of Kings: Big Heal. 1x Loatheb 2x Aldor Peacekeeper: Maybe the strongest 3 drop in the game.

Interaction with Brewmaster:

As you see this deck is like a swiss army knife. Some cards are key cards in certain matchups (like Aldor and owl are against handlock e.g.). Given that you have enough mana (from turn 4 on) Youthful Brewmaster allows you to get double the value from the cards that are especially important in a specific matchup. Just imagine how playing 3 times Aldor Peacekeeper wrecks a handlock deck completely. Or how you can silence a Sylvanas Windrunner and then get the Ironbeak Owl back for a future Sludge Belcher. Against Aggro you might want to get the Earthen Ring Farseer back.

Brewmater doesnt necessarily need to be played the turn you play the battlecry creature. It is often even more useful to play it the turn after. Then you can attack with e.g. Earthen Ring Farseer and get a full health earthen ring back on the board. This happens often against aggro decks that go face only. This healing feature is the secondary role of Brewmaster. I had games where I had my Loatheb or even Tirion damaged to a 5/1 or 6/1 and then "healed" back to full life.

The Gnomish Inventors allow you to "cycle" Brewmaster if you need some draw.

The last feature of Brewmaster is that he's a 3/2 to begin with. A Vanilla 3/2 is (beside owl) one of the best responses to a turn 1 Undertaker played by an aggro deck. He can also apply pressure against miracle or be a response to Acolyte of Pain. So he together with owl and Wild Pyromancer gives Paladin some early game options.

Board Clear:

One Key combo played in every Paladin control deck is: Equality + Consecration. It gives you some really effective board clear. So as with any Pala control deck you can let your opponent fill up the board and then "clean it" ;) This deck misses the Wild Pyromancer usually played as a second source of board clear. With all the battlecry interaction explained above and without many spells in the deck (e.g. no Humility) Elven Archer replaces the role of the Pyromancer even though it only removes the biggest threads.

Matchups:

I am playing this deck for a week now on EU legend. I went through countless iterations with other cards and I think this is the best list. This deck is favored against Handlock. You have silences, Aldor and Equality. I think it is favored against miracle with Harrison and Loatheb (possibly multiple Loathebs :) ). As in general it should also be favored against control warrior (he has more late game bombs but you'll have a lot of responses). In the priest matchup I am afraid the priest is a bit favored. But all depends on the quality of their thoughtsteals. On the aggro side I'd say this deck has a favorable matchup against Zoo. A problematic matchup is against Hunter. Even with all the anti Aggro tech Hunter has so much synergy and can put out so much damage while developing it's board at the same time. It often takes only one lucky Huffer roll or a double Kill Command draw to break your neck. But still I think if a control Pala has a chance against hunter it is this one and there is nothing more enjoyable imho in this game at the moment than beating hunters :)

Update: I added 1x Ragnaros the Firelord for 1x Earthen Ring Farseer. This change is better in every matchup except for Hunter and Zoo. So it depends on the decks you are facing the most what you play in that slot. This change comes after I got some helpful feedback on Reddit suggesting to get more winning options.

Update 2: After playing like 50 games in a row today testing Elven Archer I am of the opinion that the following changes are really favorable in aggro matchups and dont hurt all too much in control matchups. I'll rewrite the specific sections above:

I am currently testing a "hardcore battlecry" Variant of the deck. It runs + 2x Elven Archer, + 1 Gnomish Inventor; - 2x Wild Pyromancer, -1x Novice Engineer. This variant gives up on the trademark paladin board clear with Pyro and Equality. But Pyro doesnt have much interaction in this deck anyway. With Elven Archer you can only kill one specific target instead of the whole board. But you can bounce it for more targets. This variant seems even stronger against aggro. Play this variant with care though, it is not really tested yet.