Is it possible to write Arduino programs on Android phones?
Actually, it seems like it is possible. What you need is AVR-GCC to compile your code, and it looks like someone has ported it to Android.
But how you would go about getting the program onto your Arduino device I'll guess is quite a bit harder though.
You'll probably want to check out the forum post Android Hosted Toolchain.