The small (2K) RAM size is the limiting factor, not so much the code space.

You'll find a few more options if you look beyond the atmega328 in the Arduino: 'avr lisp', 'avr scheme'

The Lisps I've seen targeting AVRs have all used the atmega128 with 4KB of RAM and they still use external memory of some sort.

Scrying (w/ 64KB external RAM): http://scrying.org/doku.php?id=scrying:interpreter_notes

ActorNet (w/ 512KB external serial flash as virtual memory): http://osl.cs.uiuc.edu/nest/ActorNet-1.1.tar.gz http://osl.cs.uiuc.edu/docs/actornet/kwonActorNet.pdf

Femto microlisp http://code.google.com/p/robobuilderlib/wiki/Femto

For my own REPL-fun on AVR microcontrollers, I've gone with amforth: http://amforth.sourceforge.net