What do you do when you have no crystal

Without crystal, you won't be able to win by casting the Spell of Making, and of course, you won't be able to create troops equipped with magical stuff.

However, all things being equal, I would rather have plenty of iron. With iron, you can make stronger troops and simply conquer your neighbors.

Being an average player, though, I look forward to seeing some of the better players' take on your question.

If you have access to Iron, focus on the Warfare tree and pump out troops with high damage weaponry (swords or spears). Produce Cavalry with the charge trait so that you can usually get the first hit (A level 3 fortress with strike garrison can give them the impulsive trait, Impulsive+Charge means you'll always hit first).

If you don't have iron, load up on mana generating buildings and save up a war chest of mana, and use path of the mage champions (shoot for evoker III) to rip apart enemy armies with flame dart, fireball, blizzard, storm (whatever spells your spell traits offer you). If you're lacking in the mage department, build Bards and other henchmen with desired spell traits and level them up. 

Combine with Sun-Tzu's advice of spying well on your enemy, and you can mitigate their superior technology by anticipating their equipment and movement.

(In case it didn't go without saying, you want healthy gildar income to allow for a large army. Keep their crystal-enhanced troops busy with meat shields while your capable offensive forces win battles)

Alternative: trade for whatever resources you need. 

You can net yourself some crystal production by selecting Amethyst Vault when a conclave upgrades to level 4.  2 Crystal per season, not to be sniffed at.

Also, defeating ophidians yields 30 (IIRC) crystals.

Ctrl-N?

Why? If the game is going good and you have already invested a lot of time in this map, why would you make a new one just because there are no crystals? This is a challenging situation, but certainly not insurmountable.

They mostly joke at night, mostly.

You can also use several relatively large armies of cheap units (such as leather-armored spearmen) lead by one or two high-level well-equipped champions/henchmen to try to conquer an area that has crystal, if you also lack iron. My preference is to have a Warrior or Defender henchman with a supporting Mage champion - the henchman gets whatever army buff traits he can pick up, and the champion is a high damage caster if possible (so probably Fire Magic as a primary spell school). If you don't have a good damage caster, blessing or curse casters work decently well, though in that case you might be better off focusing the henchman on damage dealing abilities rather than army leadership abilities.

If you have access to New Pariden's shops and they have spellbooks for sale, you don't need to have an available champion and can instead create your own army casters with henchmen, leaving the champions at home as governors, or as leaders of other armies, or whatever else you want to do with them.

Should you go for large armies of cheap units, I would suggest using spears as your primary (or only) weapon - they perform better than other low-tech cheap weapons when facing high defense opponents, and are on par with similar-tech weapons against low or no defense enemies. They also require the least investment into the Warfare tech tree of any weapon aside from the club and the staff. I'd suggest leather armor for similar reasons.

If you find yourself desperate for resources and with money to spare, you can also buy quest maps and hope that the quest which spawns is one that has a resource reward. It is also a good way of training up your army, if you can afford to keep buying quest maps.

You can buy a lot of Quest maps and level Relias to an unstoppable one-man-army. Or trade the influence you gain this way for crystal. All you need are Relias and some Henchmen. The prestige you gain this way will help as well.

On random maps, there's usually something lacking: no horses/iron/crystal, poor city locations, poor starting champ, etc. That's what keeps the game different every time.

If you don't have crystal, try to avoid the magical tree (except for the important spell or whatever), it is mostly based around crystals.

Crystals is usually the most used resource lategame (for my troops anyways), so also try to bash down the factions early and only stop when either you have crystal production or you win .

If you are having trouble with the resources, you should run a rather hero focused game, with boost from mediocre trained units (if you are having trouble with both crystals, iron, horses and/or wargs), this is a tactic you can always fall back to, always try to keep a few heroes levelled pretty well.

That said, as lord Relias its not a big deal, since most of the gameplay around playing the Altar faction is focusing those semi-heroes, they don't need crystal or iron if you design them yourself, and you can buy items for them from the shop which doesn't require crystal or iron.

Sincerely
~ Kongdej

Use heroes. You're Altar, pump out henchmen army = win.