Can an exchange work which does not have control of the private keys?
This could work. Participants would need to deliver sufficient money to the exchange to protect others from their non-performance. But the exchange would never have to touch any Bitcoins.

When you sell Bitcoins, you'd have to be responsible for any decrease in the value of Bitcoins between when you sold them and when you delivered them. Rational sellers would price this risk into their spreads and try to deliver as quickly as possible.

Likely, the buyer would have to be able to cancel a buy if the seller didn't deliver. If the price had gone down, the buyer would be responsible for the difference in price.

The problem with such a service, at least today, is that it would be difficult for people to buy and sell on it. Buyers would have to wait for delivery and possibly switch offers and sellers would need to deliver quickly or risk losing money. This would result in higher buy prices and lower sell prices, which would likely discourage adoption.

It could become popular among people who want to speculate on the price of Bitcoins with leverage. You could sell Bitcoins you don't have, for example. The buyer doesn't want Bitcoins, they just want to profit if the price goes up.