I just threw this deck together to test out how Genn Paladin would work, and it's working wonderfully. I went 30-3 on two long win streaks from Rank 16 to Rank 5. I lost to a warlock because of a bad draw, and to two priests: one that opened Northshire into Shadow Ascendant, and another that used Glimmerroots to steal Call to Arms and Spikeridged Steed. Those were the only priests I faced, so this deck might just have a bad matchup against the class.
My prior versions had Sea Giants, Corpsetakers and Vicious Scalehides, but those cards didn't work very well. I'm a little iffy on the Lost Spirits, because they're not the best pulls from Call to Arms, and it sucks when you draw them, but I just wanted to make sure I had enough 2-drops and Call to Arms targets if I have to play it off curve later on. You could consider swapping those with things like Hydrologist or Bloodmage Thalnos for more card advantage, or 2-drop tech cards like Acidic Swamp Ooze or Golakka Crawler depending on how the meta evolves. Master Swordsmith, Plated Beetle, and Millhouse Manastorm aren't bad options either, depending on how spicy you want your list to be. If you want to move more to the back end of the curve, you could consider finishers like Leeroy and Val'anyr, which go well together. However, this list did well for me, so I'll probably keep it this way until I feel things need to change.
Since the meta is pretty new, there are no class-dependent mulligan strategies. Hard mulligan for Call to Arms, Knife Juggler, and Dire Wolf Alpha. Loot Hoarder isn't a bad keep either, since it allows you to have a better chance of drawing into Call to Arms on curve. On the play you want to have at least two 2-drops for turn 2 and 3, but on the coin you can have just one, because you can play two four drops on curve.
All in all, really enjoying this archetype. Might try to hit legend with it, but probably won't have the time for the grind. If only win streaks kept going through Rank 5...
Let me know if you have any questions, and I'd be delighted if this deck turns out to be tier 1 in the new meta ^_^
EDIT: After a few days of meta stabilization and playing in higher ranks, I've found that the top threats to this deck are: Baku Paladin, Warlock, and Shaman. I have had no issues with Hunter and other classes. In light of the match-up challenges, I have made the following edits:
-2x Lost Spirit +2x Wild Pyromancer
While Wild Pyro kills our own tokens and small creatures, it does wonders against opposing Paladins. Its combo with Equality is also very powerful and helps your match-up against the new Even Handlock decks that have popped up. Wild Pyro is, in general, a very strong tool for the control aspect of this deck.
-1x Truesilver Champion -1x Blessing of Kings +2x Consecration
Consecration fares a lot better against the Aggro decks out there right now, including Baku Paladin and Baku Hunter. It also combos very well with Equality.
-1x Ring the Bells +1x Rebuke
Rebuke is just too strong against the board clear classes, Level Up in Bakudin, Burn in Hunter, etc. Against Warlock, an early copy of this after a Call to Arms or some sort of swarm ensures that you can seamlessly go into Tarim. Against other classes, having this in the late game really helps you snuff out their big swing spells, or expensive board clears in the case of Shaman. I have not yet regretted having this card in hand and using it.
-1x Tirion +1x Silver Sword
I took the advice of the commentors here and made this swap. While Tirion is great in the value game, he's not very well suited for the current meta. Silver Sword ensures that you have an easier time closing out the game against control decks, before they outvalue you or lock you down. This is especially the case against Shaman, where you want to finish them off asap.