You don't connect the Android to the PC with a cable. You use Wi-Fi or Bluetooth. You don't keep the private key on the cellular because it can be easily stolen. Stealing the PC AND the cellular is more complex (you can easily hide the cellular when you don't need it). Yes, it's perhaps possible to hack a cellular through wi-fi, but it's quite complex, and it's model-by-model. There isn't a single-hack that works for everything. It isn't totally fool-proof but it raises the difficulty of an hack very much. Especially if you consider that economical Android cellulars will multiply in the next year or so.
I am just afraid that Android is as big as a target as Windows for exploits in the future. I would think a more custom OS that runs on the old cheap Android hardware would be a little more secure. I understand now why you want to keep the private keys on the PC and download them to the Android device temporarily. Unfortunately if someone has enough physical access to the cell phone and PC you could easily just take the hard drive or copy the keys to a bootable USB stick. Once a site is physically compromised there are no safe bets. A stolen cell phone that has a password protected wallet in it would not be worth much to a thief without already knowing the pin/password or monitoring the phone with screen capture or some other monitoring method like a webcam from the PC.
-Dukejer