I doubt you would find the immutable aspect in Erlang a problem in practice. I don't know MzScheme, but Erlang has a its own very different philosophy. I suggest Joe's thesis as an interesting read.
Well I found it a problem when I tried to program a Sieve Of Eratosthenes for project Euler. Also when I considered a grid based alife simulation. I guess the only way would be to use a process per cell?
Sometimes the mutable structures get passed around in the function arguments, so you might do a sequence of tail recursive calls and on each call you pass in the next board state to the same function. I would hope the Erlang Questions mailing list would help you if you posted a small example and explained your troubles to them. There are lots of very clever Erlang people there.
http://www.sics.se/~joe/thesis/armstrong_thesis_2003.pdf