Can private keys be securely stored on blockchain? Ok, I know that blockchain is public knowledge. But, than, there are experiments like zcash which encrypt sender receiver and amount information and they still work.

I'm considering whether p2p blockchain arbitration service is possible. For example, you want to exchange ETH for BTC. A blockchain generates 2 addresses, one of which is for BTC, other is for ETH. Once both addresses are funded, funds of both are forwarded to the recipients. To do this via blockchain, there should be a secure way to store and use private keys on blockchain.

Is this completely impossible, or are there any indications that one could do something like that?
There is no encryption involved anywhere in a blockchain. There are no keys to encrypt with, as every node has the same information as all others. Cryptography is involved, but for signing/proving. Not for encrypting.

Even in the zcash case, encryption is not involved. All wallets do is prove to the rest of the network that they had the funds they're spending. The only difference compared to Bitcoin is that it reveals less information in doing so, and as a result, the proofs are much more complex.

blockchains don't generate private keys - that doesn't make sense, as the chain can be seen by everyone.

Wallets do have private keys. They're never shared with anyone. They hand out the corresponding public keys in order to be paid, and use the private key to later prove to others they own certain coins.

The example you're describing with an exchange occurring between two chains is possible using a technique called cross-chain atomic swap. It relies on a hashlocked​ transaction where the first wallet that moves its money out on one chain reveals a random value that hashes to a value that is known ahead of time. The other party then uses this preimage to unlock funds on the other side.