I've done some searching about the possibility to being able to compile arduino sources on an Android device and upload it to the Arduino via USB.
Well, I've learned that the stock Android doesn't support the use of the USB port, so it could only be done by rooting your device.
For this to work your device should also be able to use USB OTG, as it would have to be the server in the connection to the Arduino.
Here's the best shot so far to be able to implement this idea.
However it is possible to communicate via bluetooth or WiFi with the stock Android, but for the Arduino that would require an extra shield (XBee) or a specific board (Arduino BT).
There is a project for this, called Amarino. It is designed specifically for communication between Android and Arduino by Bluetooth.
Also I found that the stock Android source for HTC phones is shared here.
This can give people hints on how to circumvent the software limitation.
If rooting your device is an option, Cellbots is the way to go.