Cuckatoo Cycle is a proof of SRAM. Cuckatoo32, as used in some cryptocurrency, requires 512MB of SRAM to solve efficiently (in addition to 512MB of DRAM).
The solution process is dominated by writing and reading of individual random bits.
Currently available Cuckatoo32 ASICs only have 64MB on-chip SRAM, causing an 8-fold reduction in efficiency, which still outperforms GPUs.
Litecoin/Dogecoin use an scrypt-based consensus algorithm; scrypt was designed to be "memory-hard" as a way of preventing ASIC-based brute-forcing of password hashes. So that's a "proof of having some memory", at least. (I think the relevant knob on the call to scrypt could just be turned way up to get a "proof of having a lot of memory.")
I believe Ethereum's ethash consensus also works this way, which is why there aren't Ethereum ASICs.
A good PoW should have very fast verification. That's why scrypt makes a poor choice of PoW (technically, the hashcash PoW with scrypt as hash function). It's quite possible to have an instantly verifiable memory hard PoW, where only finding solution takes lots of memory, while verification takes none. For example, Cuckoo Cycle and its variants [1].
