You don't. Cheat all you can, abuse everything abuseable, run your daily deck, pray to RNGesus and maybe you have a chance. Used to be easy with Electrostatificationized, but after its changes it's pretty hellish in there.
Thanks. I'll just give up, then. I was really hoping to beat all the campaigns on legendary, but some of them really seem impossible. I thought maybe there was some IS combo or something that I was supposed to use -_- Some of the last level legendary maps just seem impossible. Some you don't even get to spawn runes unless you scry. I beat a few of those, but there was one where you start with 3 units with ~200 hp each, and the opponent starts with 4 and one of them is a range 3-10 dmg 30 hp 1000 unit that attacks from lava...
I ended up beating that map and most of the other legendaries, too. If anyone else is new and looking for a compstomp lineup, this is what I made that works. http://www.poxbase.com/deck/Ch4CqYCtFCwGCgOc3ZCgBS55S6Tsys5tS2-s73SPsAs5jr2Le2wE1O Rageband + Dervish = millions of damage (Base Berseker 1 + rageband berserker 2 = 9 speed and immune to careless, too) Righteous Deflection to stall Horn of order to pump dervish, etc Minotaur Gladiators to survive early game Acidic Gale to insta-kill bosses Sacrifice to dump a couple terrible starting champs to jumpstart the lineup Bubble/font for emergency life and spot cleanse Doctors for nora gen, healing and mutating dervish into even bigger monster Mine Fields to clear massive clumps of units Transfusion to double dervish's dps for a turn Mimic to do hilarious other things (Whenever possible, I try to get a pouncing 100 attack/30 def minotaur, otherwise steal defensive upgrades for dervish) Demolish for relic objectives Negamage for severe summons Purge to remove base invuln and win regardless of win condition Rest of champs just backup for rageband and a reliable early game. Although I think dervish is the best, you could replace the race theme with elves + elvish prodigy or firk + firk sentry or any other race with a good sentry ability somewhere. Rageband snowballs to instant win pretty quickly.