Can USB data transfer between Arduino and Android with the 5V power line disconnected still work?
It is not unusual to have a USB device draw its power from a source other than the USB connection; such a configuration is called "self-powered" and the device's datasheet will give the exact schematic, components, and sometimes even PCB layout to make such a thing possible. It is resistances placed on the D+ and D- lines that announce presence rather than any connection to the 5V line.