I have heard of four (attempted) solutions to this, and none of them is perfect:
1. Gateways (à la Ripple)
Though exchanges themselves are decentralised, the "coloured coins" they exchanged need to be issued by a trusted (centralised) authority who will exchange for example 10EUR/USD for 10cEUR/cUSD which can THEN be exchanged for BTC or other currencies.
2. IOUs (à la Ripple)
Rather than trading actual currencies, people make interest-free "loans" and trade the debt. For example, you give me 1BTC for a 150GBP "IOU", which you can trade on to other people with the promise that I (or others trading IOUs in the same currency) will buy it back for 150GBP worth of BTC/some other currency. Of course this relies on people having confidence they will be able to trade the IOUs back to Bitcoins.
3. Magic (à la Harry Potter)
Some sort of coloured coins are distributed that by convention just happen to be pegged exactly to EUR/USD/GBP or whatever, and eventually the convention becomes so universal that people stop distinguishing between cEUR and EUR.
4. Automatic "monetary policy" (à la Mastercoin)
One suggestion I have seen, I think it might have been for Mastercoin but I'm not 100% sure, was that some sort of decentralised "system address" would hold an excess of for example cEUR, and when the BTC value of cEUR started to climb above EUR more cEUR would be released into the market, and if the value was below EUR then the system would buy back some cEUR for BTC to bring the value back up. How the system would track the value of the EUR however I don't know. Presumably it would be a mathematical system not relying on external feedback, so would try to approximate a certain value that was equal to the value of the EUR at the time of implementation, which obviously could change over time and the correlation become broken.
Imagine if there existed a low-friction, cross-border, P2P system for insuring arbitrary contracts via performance bonds.
It would make number 2 a lot easier to achieve in practise, wouldn't it?
I think the main issue with number 2 is this:
Person A issues 150cGBP for 1BTC to person B. EITHER cGBP can ONLY be traded back to A for bitcoins, in which case A is a centralised exchanger, OR multiple exchangers agree to accept each other's cGBP, in which case there is nothing to stop person C1 issuing 1500cGBP to their other account C2 for 1 satoshi, then trying to exchange those 1500cGBP to person A for 10BTC.
With a performance bond in the latter scenario, there will always be situations in which people can make a profit from being dishonest larger than the performance bond. There could be a rating system attached to it, but then either everyone is given a fair chance before their rating goes down in which case scams will still happen, or else everyone starts at zero in which case they will never be accepted into the system and the same few trusted players will control the market.
In the former scenario, where each issuer is a "centralised" exchanger, and for example A issues caGBP, C issues ccGBP etc., then the equivalence of those "currencies" will be purely circumstantial; value will depend both on the BTC price being offered by each exchanger, and on the trustworthiness of each exchanger; for example, A and C might both be selling 150caGBP/ccGBP for 1BTC, but if there is more confidence in A's ability to redeem the IOU then there will be more demand for caGBP in secondary markets and thus a higher price. Besides, these currencies would only correlate to real GBP by coincidence, rather than having any strong equivalence. In this scenario, how a "performance bond" would work I'm unsure, for how can you say that A is acting in a manner "truer to GBP" than C?
Perhaps the cGBP issue transaction could be backed by some sort of proof-of-stake/proof-of-burn, to ensure it was purchased for the "correct" number of BTC (but how that would be calculated I don't know).
EDIT:
There is another scenario, sort of like a hybrid of 2 and 3. The currency STARTS OFF being issued by a centralised exchanger (A) for say 1BTC = 150cGBP. These cGBP are traded around at roughly the same rate because everyone is confident that A will redeem them for bitcoins again. One day A vanishes, but so many of his cGBP have been in circulation for so long that people have been buying them for 1GBP worth of BTC by convention, and they continue to be traded at this value.