You can create a contract unique to each user, which in turn deploys wallet accounts. But the cool thing with this is that you don't actually have to deploy those wallet accounts until you want to or need to which can help you save significant gas costs. Why? Well that's because we can easily calculate the addresses of new contracts that will be generated by a contract.
Contract accounts start off with a nonce of 1, which is only increased during transactions from the contracts invoking the create
opcode, so we can easily calculate addresses off-chain or on-chain. I wrote a contract that demonstrates this:
https://github.com/postables/Solidity-Modules/blob/master/Contracts/AddressGenerationCalculator.sol
Or if you don't want to go the whole contract route and don't care about centralization or security risks, you could generate the public-private key-pairs on your server, and create a web app to let people use their pre-generated wallets.