I found the "trick" to this level (some levels have tricks that decrease the difficulty significantly), and, as I thought, it involves the Free Pegasus Relic.
1) Set up a strong defense. You shouldn't run out of resources because this level can be done fairly quickly, so make 1 or 2 layers of walls near where the trees were that they burned down. You won't need much food in this scenario - 2 fishing ships and one Citezen should suffice.
2) Make loads and loads of Cherioballistas. I mean around 20. Then make around 5 Arcus. Once you are at the pop limit, turn your Arcuses into Heroes. These will be very useful against the Frost Giants that they send at you.
3) Make loads of towers and a palace near those walls. Now, remember that lone food Citizen we have? Well, make him build a farm near your defenses. He can farm when the enemy is not attacking, and when they are attacking, he can continually repair the walls (the Rams will knock them down otherwise). He shouldn't be attacked because they don't have any ranged weapons except a few Throwing Axemen.
4) If/when they use frost on your army and your food/repairing villager, just bring another 2 villagers to your walls and continually repair them while your towers/palaces keep firing.
5) OK, once your defense is solid and you've fully upgraded your units (you only need Heavy Archers, Heavy Charioballistas and Armoury Upgrades remember), make a tower at the very west end of your plateau. With the relic that starts on your plateau (+8 Building LOS), Signal Fires and Carrier Pigeons, it should have awesome LOS. Use this LOS to time-shift a Counter Barracks or Barracks over the plateau. Then, make a Turma or Contarius from this building.
6) Send the Turma/Contarius to the very west of this plateau, and then hug the left hand wall and send them northwards. Eventually, after some trees, you'll see an opening protected by some fences. Go through here to find the Free Pegasus Relic. Turn the Turma/Contarius into a hero to pick up the relic, and then time-shift a temple near where the relic was. Place the relic into the temple and then delete the Turma/Contarius.
7) Set all of your temples to have a way point near your TC. Once the pegasus appears, send him to the very east of the map (hugging the south/east edge to avoid being shot down). Then, hugging the north/east edge of the map, send him to the first temple. Deconstruct it, and time-shift one of your temples in its place.
8) Send the pegasus to the middle temple and repeat the process above.
9) To get the the left-most temple, you'll need to go all the way around Odin's Tower to avoid being shot down by the towers and Hill Forts here. So, hug the north/east edge and make your way North, then hug the north/west edge and go to the temple. Deconstruct this temple.
10) Unfortunately, the nearby Hill Fort prevents you from time-shifting in a temple of your own, so make sure your army is maxed out, and then Vortex your units next to the Hill Fort (you should have your 2 starting Destroyers and loads of Cherioballistas that have the Burning Pitch Upgrade [you start with this upgrade on this level] so it should go down fast). Once you've Vortexed in, the Hill Fort will be busy, so time-shift a temple where the 3rd temple was. Then send Kastor to Odin's Tower (hugging the east side of the cavern to lessen the damage from towers etc.) and then use the Wonder Deconstruct God Power on Odin's Tower to win.Phew! The next level is extremely hard also