I'll take the simplest case. Exchange of USD to BTC and back. Payments: BTC - the blockchain, USD - PayPal.

I'll take for granted, that someone will write P2P matching software which everyone runs on his computers.

 + Damn convenient
  - Security, security, security

Next the risk of counter-party chargeback. How it can be reduced?

• Reputation.
• Proof of work. In order to place an ask/bid some rather expensive computation has to be performed. So that, say, only half of existing bitcoins can be exchanged every 24 hours. The same is true for holders of PayPal accounts, which will also have to provide proof of work in order to ask/bid. Or maybe only for them, since BTC transactions are irreversible.
• Insurers. Can work, but introduces some elements of centralization. Like exchanges.
• Automatic mixing of payments. Not receiving payments from one individual account, but from many. Ideally so, that ratio of fresh/untested PayPal account will be less than 10% initially and 1% when the system will be established.
• Different exchange ratios for tested/tested PayPal accounts

.

So this is my proposal. Feel free to rip it apart. I'm not (yet) emotionally attached to it