Stateless hash based public key cryptography?
You can build a gigantic, enormous tree that has capacity for up to $2^{80}$ one-time signatures (say).  Then, each time you want to sign something, you randomly pick a 80-bit value and use that to select which of the $2^{80}$ subtrees to use to sign the message.  As long as the number of messages you intend to sign is much less than $2^{40}$ messages, a collision is unlikely.

It takes some extra work to make this work.  In particular, if your tree used only hash functions, then to precompute the public key, you'd have to do $2^{80}$ work to populate the entire tree -- no good.  So, in fact we do a multi-level tree where the entries at one level are used to sign a subtree the next level down (signed, using Merkle-Winternitz signatures).

For more details on how to make this work, you can see, e.g.,  https://www.imperialviolet.org/2013/07/18/hashsig.html or https://www.cdc.informatik.tu-darmstadt.de/reports/reports/BDKOV07.pdf.

This does increase the size of signatures and the amount of computation needed a bit, but if you want a stateless scheme, it might be viable.