Bitcoin is UTXO based, so you can use an HD wallet(BIP32) to get a new address for each transaction to protect your privacy. However, Ethereum is account based and each account has a single address, but it is possible to implement an HD wallet for Ethereum. I think there is already such wallets as Jaxx which provide such ability.
So to answer you, if your privacy is crucial to you, please use an HD wallet for Ethereum. Mist don't offer this option.
Read more about HD wallets https://github.com/ethereum/EIPs/issues/84
Web3j documentation explains most of the things. I found this android ethereum wallet created using web3j. Might help you. https://github.com/matthiaszimmermann/ethereum-paper-wallet
Alternate:
I would recommend cross-compiled go-ethereum for Android. This is a light client for mobile devices and does not require you to download the entire blockchain. After importing maven dependency for the same you will get an API to interact with the blockchain (example program). You can create new account, check balances and send transactions.
The only thing is that Android API is not documented hence it is difficult to work with it. I hope the developers would do something about it in the future.
Updated:
Ethereum don't have have an Android API till now, but auto complete tools in IntelliJ or Android Studio will help you. You can refer to the following code to get a little understanding of the API.
Ethereum creates a keystore file whenever you create a new account which is something like this:
{"address":"bab565b65fede.....7a98ab7c330c","crypto":{"cipher":"aes-128-ctr","ciphertext":"ab4913efa82.......d3d5fe335025596","cipherparams":{"iv":"ece5ac32........4942b58"},"kdf":"scrypt","kdfparams":{"dklen":32,"n":262144,"p":1,"r":8,"salt":"bcd244b8ee3def42........0d4c78758d858d3502"},"mac":"1c618efa10d54......3f5a3e4377"},"id":"0e0416d0-2a58-43c9-86cc-2c1eaa11957b","version":3}
Where "address" is your wallet address and "crypto" constains your private key enctypted with a passphase. So ethereum will help you manage user accounts, you just have to create a mapping between usernames and wallet addresses.
Best Answer
You don't have to save wallet to file. You can extract the low-level code yourself. Check my answer here Generate private key and address using web3j