You can do that with xPriv paper wallet, but unfortunately there's no BIP38 for that. There should be.
So I scan the xpriv QR code into Mycelium, it checks which unspent outputs exist for that xpriv, picks some, and sends change back to another of the addresses generated from the xpriv code?
That sounds like a good solution, except that due to the lack of encryption in the xpriv QR code I have now gone from losing all my coins if my phone gets stolen to losing all my coins if the QR code gets stolen.
I was hoping for an HD solution where at least some of the information needed to spend the coins is in my head. Like as a passphrase.
Edit: Is there any such wallet available for Android? Or any open-source wallet for Android that such a feature could be added to?
As I understand it, Mycelium isn't open source and so adding such a feature isn't allowed.
Correct, correct that losing paper wallet is a concern, and I think we need to update BIP38 to have standard for encrypting xPriv keys.
Mycelium is open for anyone to look at and add features to. The only restriction is that you don't publish your own wallet, and whatever is added goes into the official app.
I'll bug the devs about this.