What about a remote blockchain? A symlink over the Internet, or a blockchain 'server' that can scan the blockchain for these Android clients whenever the Internet is available.
We will be releasing an android client soon, coupled with a server that does exactly this.
For Linux, it would be enough to have a frontend that just connects to the machine via SSH or similar secure protocol and talks to bitcoind. I assume the Windows client has a similar "headless" interface, and there are SSH ports for Windows as well, though I've never used them so I don't know how easy they are to use.