What you want to do is completely possible, but at this moment in time it isn't exactly
convenient. Very soon, though, it might be easy.
First, a few questions.
1. What Bluetooth modem are you planning on using with your Arduino?
2. What version of Android is running on your Android device?
3. Is Bluetooth communication available on your PC?