What are the available interactive languages that run in tiny memory?

A homebrew Forth runtime can be implemented in very little memory indeed. I know someone who made one on a Cosmac in the 1970s. The core runtime was just 30 bytes.

I hear that CHIP-8, XPL0, PicoC, and Objective Caml have been ported to graphing calculators. The Wikipedia "Lego Mindstorms" article lists a bunch of programming languages that allegedly run on the Lego RCX or Lego NXT platform. Do any of them meet your "live coding" criteria?

You might want to check out the other microcontroller Forths at the Forth wiki . It lists at least 4 Forths for the Atmel AVR: amforth (which you already mention), PFAVR, avrforth, and ByteForth.
(Links to those interpreters, as well as this StackOverflow question, are included in the "Embedded Systems" wikibook).

I would recommend LUA (or eLUA http://www.eluaproject.net/ ). I've "ported" LUA to a Cortex-M3 a while back. From the top of my head it had a flash size of 60~100KB and needed about 20KB RAM to run. I did strip down to the bare essentials, but depending on your application, that might be enough. There's still room for optimization, especially about RAM requirements, but I doubt you can run it comfortable in 8KB.

Some AVR interpreters/VMs:

1. http://www.cqham.ru/tbcgroup/index_eng.htm
2. http://www.jcwolfram.de/projekte/avr/chipbasic2/main.php
3. http://www.jcwolfram.de/projekte/avr/chipbasic8/main.php
4. http://www.jcwolfram.de/projekte/avr/main.php
5. http://code.google.com/p/python-on-a-chip/
6. http://www.avrfreaks.net/index.php?module=Freaks%20Academy&func=viewItem&item_id=688&item_type=project
7. http://www.avrfreaks.net/index.php?module=Freaks%20Academy&func=viewItem&item_id=626&item_type=project
8. http://www.avrfreaks.net/index.php?module=Freaks%20Academy&func=viewItem&item_id=460&item_type=project
9. http://www.harbaum.org/till/nanovm/index.shtml

Have you considered a port in C of Tiny Basic? Or, perhaps rewriting the UCSD Pascal p-machine to your architecture from Z-80?

Seriously, though, JavaScript would make a good embedded scripting language, but I've no clue what the minimum memory requirements are for the VM + GC, nor how difficult to remove OS dependencies. I played with NJS a while back, which could possibly fit your needs. This one is interesting in that the compiler is written in JavaScript (self hosting).

Have you considered simply using the /bin/sh supplied by busybox? Or on of the smaller scripting languages they recommend?

None of the languages in the list in the question or in the answers proved satisfactory for the requirement of super easy compilation and integration into an existing micro controller project (disclosure: I didn't actually try every single one of the suggestions).

I found instead tinyscript which is a single .c+.h file that compiled with the rest of the source files on my project with the only additional configuration required being to provide a void outchar(int c) which can be empty if you don't require output from the scripts.

For me speed of execution is far less important than ease of build and integration and interop with C, as my use case is mainly just calling some C functions in order.

I have been using in my previous work busybox on a BlackFin.

we compiled perl + php for it, after changing s/fork/vfork/g it worked pretty good... more or less. Not having an MMU is not a good idea. The memory fragmentation will kill the server pretty easily. All I did was:

for i in `seq 1 100`; do wget http://black-fin-ip/test.php; done

It died while I was walking to my boss and telling him that the server is going to die in production :)