Then you'd end up with potentially presenting the same address to several users, as there will always be some lag time between presenting the user an address and the user sending something there.
The only thing to prevent this is to create some accounts on your service (which is something I want to avoid) or doing ugly things such as using IP addresses to distinguish between current users...
I'd say you have sessions for your users at least, to do basic things like shopping carts or even sticky load balancing. so map those to accounts and you will only ever need as much accounts/unused addresses as concurrent sessions. IMHO, bitcoind gives you some great tools at hand if you want to get things up and and running quickly.
If you want to build things neatly, build on bitcoinj/BOP with deterministic wallets, optimise wallet performance once needed, and then contribute your changes back instead of sitting on them.
blockchain.info is also not perfect, as you will have archive addresses to keep wallet performance up:
http://blockchain.info/api/blockchain_wallet_api