Can I terraform outside of my turn, or during my turn in some other action?
Yes, if you ever get a spade you must use it immediately, or forfeit it. The only way to get a spade outside of taking an action on your turn though is the end-of-round cult bonuses that give them.

From the rulebook:


  You may not save Spades for future Actions. Spades need to be
  used immediately. 


Note that the spades that you get for the cult bonuses must be used by themselves; you cannot also spend workers to terraform more, nor can you build a Dwelling at that time. Those are things you can do in addition to getting spades when you choose the terraform and build action or a power action that gives you spades.