The fastest way to level is hands down by playing games against real opponents. This can be done in either play mode or Arena.
Arena may be best (if you're doing well for gold or don't mind spending the money) because you get to use cards you wouldn't have and the wins and losses still grant you experience. The arena cards you get to use would grant you a stronger deck for that class and would give you (a theoretically) high chance to win than with the basic decks you have. Please note that you will only have the option between 3 classes in arena and may not get the one you need to level (credit: ChrisHateZ)
You can still create custom decks even at low levels. Whatever common cards you may have earned can help in this cause so you can build stronger decks. In play mode, you can gain the experience in either casual or ranked. There is no experience difference gained there, just your ranking.
Also, games that last longer (in the same level) generally give more experience than quick ending games in my experience.
The only reasons to play against the expert AI is to test a deck you are building before putting it out into real play and to complete the quest that requires you to defeat all Expert AI opponents (which will reward you will gold).
In a deck built around flooding the board with minions, I've noticed Hunters tend to be by far the largest issue, because in addition to having access to easy and cheap board clear, they also have unleash the hounds, one of the most insane 2 drops in the game. I personally have two decks, paladin and shaman, that are built around having a large number of small minions on the field.
Firstly a word of advice based on your commented deck list. If your do really enjoy flooding the board using your power, I would highly recommend you consider cutting down some on your four drops and increasing your number of three drops and maybe even two drops. The advantage of this is that, it makes you more likely to be able to use all your mana in a turn for maximum efficiency. For Instance:
- Turn 2: Use Power or play relevant 2 drop, depending on board state and opponent power.
- Turn 3: Play 3 drop
- Turn 4: Use Power and play relevant 2 drop, OR play 4 drop.
- Turn 5: Use Power and play relevant 3 drop.
Alright, regarding your specific issues against hunters, one of the best counters to unleash the hounds is high toughness taunt creatures, or having a number of taunt creatures. The big issue is that most hunter decks will be running 2 silence owls, so oftentimes they'll simply silence your large taunt creature, and then attack past it. Some possibilities to fill this role include:
Sen'jin Shieldmasta: Hands down one of the best taunt minions in the game, Sen'jin can usually eat up anywhere from 3-5 hounds from unleash the hounds, depending on how much support your opponent has for the unleash. In addition, Sen'jin is relevant against a large number of other decks unlike some other large taunt creatures. I would definitely consider running 2 of these if you tend to have issues against aggro decks. The big downside of him against hunter decks, as is the case with most bigger creatures, is he dies to a kill command.
Tirion Fordring: A very powerful legendary creature, if you have him, I would highly recommend running him, as he's hard to kill and still impactful upon dying. The big issue with him is that he is one of the biggest blowouts if he's silenced, just becoming a measly 6/6 for 8 if he is.
Abomination: Abomination is, in my opinion, a very underrated minion. He is amazing against Unleash the Hounds specifically, almost always clearing all the hounds on his own, in addition to any potential support your opponent might play, such as timber wolf and starving buzzard. The big downside of him for you is that he basically acts like an exploding trap, most likely killing all your token minions.
Defender of Argus: Defender of Argus is an amazing creature, especially for a paladin, who is easily capable of making sure he has the creatures to use it with. The big downside of him in this case is that if your opponent has Timber Wolf, their hounds will just trade for your 2/2 soldiers. I would still recommend at least running one of him in your deck, if not two, because there are many times that he is relevant.
Sunwalker: One of the hardest to straight out kill taunt creatures, sunwalker can be very impactful upon the board. The big downside of him is that he's highly susceptible to silencing, and is somewhat high costing, especially if he gets silenced.
Fen Creeper: Generally considered to just be a worse version of Sen'jin, he is still not a bad consideration to put in to the deck if you're having that much difficulty against hunters. The benefit that Fen Creeper has over Sen'jin is that he won't die to a single kill command, taking both a kill command and a hound to kill, and still eating up between 3 and 6 hounds if they don't have kill command.
Sunfury Protector: A tiny version of Defender of Argus, I would be hesitant to run this in your deck, since you're most likely going to have only small minions to use her with. Still, her ability can be very relevant, as she'll force your opponent to clear two of your minions before they can attack you.
Mogu'shan Warden: As a last ditch effort, if Unleash the Hounds is absolutely the bane of your deck, I would run Mogu'shan. He is often very irrelevant against opponents, but against Unleash the Hounds specifically, he is one of the best minions out there. Again though, he's not very good against most other decks.
Worrying about clearing the board of an unleash the hounds after their turn is less of a big deal, as you should probably be saving your consecrations for just such an occasion if possible. If that is a concern though, you can also add Avenging Wrath to your deck, as it's an excellent board clear against Unleash the Hounds, and in general, is just a rather good spell, at worst being 8 damage to the opposing hero for 6 mana.
Regarding the other aspects of the hunter, having big taunt creatures also helps to avoid your creatures' divine shields from being removed, by protecting the smaller divine shielded minions. In addition, divine shielding a Sen'jin Shieldmaster or Abomination can be pretty powerful.
In respect to the explosive trap, unfortunately, there's not many counters to it in a paladin deck besides playing around it, or using divine shields. If you're truly worried about it, consider doing little other than using your power until your opponent uses their first explosive trap. If you bait out an explosive trap, you can much more confidently attempt to establish board control by playing a number of cards from your hand after it explodes. Divine shields though do suffer from the issue of being easy to trade a small minion in to remove it. It is why I would probably not run Hand of Protection, but would definitely still run Argent Protector, as a 2/2 with 'Give a friendly minion divine shield' is pretty good.
Best Answer
There are many cards one can play around and that one should expect, knowing the capabilities of all classes and the common tactics is necessary for high-level play. All that would be far too much for a single answer here, but there are a few devastating plays that are useful for new players to know.
I've restricted my list to the most dangerous cards or combos, only those that can completely turn the game if you are playing into them unaware.
Mage
Paladin
Hunter
Shaman
Priest
Warrior
Druid
Warlock
Rogue
Neutral
The list is incomplete, feel free to add to it (this post is community wiki)