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.