I do not see why this would be impossible.  I see the biggest problem is that the time it takes to transact an exchange and also guarantee payment between both parties.  I think that maybe a rating system would help with the guaranteed payment.  Start small with exchanges and earn a reputation for honest exchanges.   As for the time it take for a transaction to take place I would think that a block chain would have to solve blocks quicker then 6 an hour.  Maybe something similar to namecoin.  With a high enough transaction fee I could see transactions taking priority and moving from peer to peer rather quickly.  If you are not in a rush you could use a lower transaction fee.  Money could be exchanged in person(long/lat), western union, paypal, dwolla, coinshop/merchant etc.  Part of the transaction and exchange would be listing your payment choices and bids or asks to find a suitable person or business to exchange with. 

- Dukejer