After another day of messing around compiling Mono, I finally got it working on Android out of the box. The final hurdle was to tweak a few environment variables at build time to pass the "--dynamic-linker /data/data/com.koushikdutta.mono/ld-linux.so" option into the linker. This way the mono binary will actually find the dynamic linker at a valid location in the Android file system rather than fail with a "not found" error.
The application on the market contains the Mono runtime, which will be unpackaged on first run. It will allow you to run simple command line applications from a tool like Terminal Emulator. Here's some more Mono on Android action, sans Debian. The video shows the simple installation followed by a demonstration of the "Hello World" program that is included with the package.
Note that the application is downloaded, installed, and executed, all without root permissions. There are still some outstanding issues though. If you watched carefully, you will see that I redirected stderr to /dev/null. This is because Mono not running under Debian reports a couple of assertions and errors; once upon starting up and again upon exiting. But they don't really seem to be affect anything from as far as I can tell. It is something I'll need to look into. But first... calling into Mono from Java/Dalvik.