On the fly signatures and zero-knowledge
Actually, it has not really to do with zero-knowledge. 

From any public-coin three move identification scheme you can derive a secure signature scheme (in the random oracle model) using what is called the Fiat-Shamir heuristic. Many of these protocols represent honest-verifier zero-knowledge proofs (like the Schnorr, GQ etc. protocols). Now, every such scheme has basically the same structure (choose randomness, compute commitment, compute hash, etc.) and thus is a candidate for the precomputation of the first two steps as you describe it for the Schnorr signature.