Cross compiling static C hello world for Android using arm-linux-gnueabi-gcc

Try specifying the architecture/cpu. It sounds like the compiler is creating code with a higher architecture version than the emulator can handle.

This might work:

arm-linux-gnueabi-gcc -static -march=armv5 hi.c -o hi