I like your Paladin team. In my case, the AI seems to know when I am running Paladin and starts targeting him for destruction. It is uncanny. I usually only break him out with cards beyond what you are describing in your video—example team: Celestasia, The Great Maw, Paladin, Prismatic Orb (Holy Banner) /Maester of Air, Lord of Devas/.
Early Monster Mash
You mentioned Golem which is a nice card. One uniquely monster team I have run is Golem tossed into the mix with Night Terror, Marsh Raptor, and Chimera. It has Monster General (+2 Armor, +2 Life, +1 Magic) and some interesting damage mechanics and statuses to toss at your opponents. Golem is mainly there to keep the heat off the other three monsters, two of which target the weakest enemy and one that poisons and burns the strongest. All are Ultra Rare or lower, Golem being Common. You can substitute in other monsters like Mist Stalker or Gorgon as well.