Is the following key stretching algorithm as memory hard as I think it is?
Let $n$ be the number of "memory cells", and $t$ the number of iterations (i.e. the three steps you describe in your question). Then we see that at each iteration, each cell has an equal probability of being picked. Then, the probability that any one cell is not selected on this iteration is:

$$1 - \frac{1}{n}$$

And hence, the probability that one cell is never selected, is:

$$\left (1 - \frac{1}{n} \right )^t$$

And so if the attacker uses an intelligent memory cell addressing system, he really only needs:

$$b \cdot n \cdot \left [ 1 - \left (1 - \frac{1}{n} \right )^t \right ] ~ ~ ~ \text{bits of memory}$$

Where $b$ is the cell's size. For $b = 256$, $n = 128 ~ \text{MB} / b = 4 \cdot 10^6$ and $t = 200000$, we get:

$$\text{Memory required} \approx 6.25 ~ \text{MB}$$

Far less than the $128 ~ \text{MB}$ expected. And that's a lot of iterations. For $t = 2 \cdot 10^6$, we need $50 ~ \text{MB}$.



Now look at the probability of a cell only getting used once (then saving its value is irrelevant), and watch your scheme crumble. At least, if I understand it properly. To be specific, your logic fails at this point:


  Intuitively, it seems to me that any algorithm that wishes to find the
  digest after the last iteration of the above loop needs to invest in
  at least enough storage to hold all cells that have been modified.


In which you didn't consider that with your current key stretching algorithm, most cells won't be modified more than once unless you have a ludicrous number of rounds, so you don't need to invest memory to save those cells (since they are zero-initialized). Take a look at how scrypt does it - you can choose to not use any memory at all if you want, but you'll need to spend a lot more computational power. It's a trade-off. In your scheme, there is no trade-off. I can choose to not spend memory... for free.

In other words, your algorithm is a bit too simple. What you are missing is a step that initializes all the memory cells with pseudorandom (not random-access) values derived from the key, in which case storing them would be a necessity, and the scheme would a priori not be subject to this weakness.

Of course, this is all for fun and academic interest. If you need a memory-hard KDF, use scrypt.