how can they not have access to the private keys? If the wallets are PHYSICALLY hosted there, they have access to everything.
blockchain.info does not "PHYSICALLY host" your wallet there. The "wallet" consists of a bunch of javascript programming that runs locally on your web browser. When you create a new private key, the software running locally on your computer in your web browser generates the key (not their server). When you sign a transaction, the software running locally on your computer in your web browser generates the key (not their server).
The software in your browser encrypts the private keys with your password (and does not send the password to their server). Then it sends only the encrypted private keys to their server. That's all they have access to. When you need to do something with the private keys, they are sent encrypted from their server to your browser where the javascript programming decrypts them locally to use them. This really isn't much different than storing an encrypted copy of your wallet file somewhere offsite and online (like dropbox or google drive) and then re-downloading your local wallet new each time you use it.
If you don't trust the encryption used to encrypt the private keys, then how can you trust any of the cryptography used in any of bitcoin at all?