You don't need to have this pregeneration to get 99% of contents into a forward secret system. Signal does it to encrypt the first few messages of a conversation. The rest is handled by advancing the cryptographic ratchet in each message. You could easily have the first message to a user contain the start of a cryptographic ratchet and response messages advancing it.

After the first back and forth communication, it's encrypted forward securely, with a full rekeying happening in each back and forth interaction. This does involve state, yes, but it works 100% asynchronously. In fact I think it's also compatible with the multi device plans that Threema has.