I have heard of four (attempted) solutions to this, and none of them is perfect:
Nice summary, thanks!
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.
I think this is the most promising approach IF we can get truly serious player involved in this.
Ideally, a company which owns underlying assets should be 100% isolated from trading and other activities. Basically, it should be a trust (ETF-like) which simply owns USD and does nothing. Companies responsible for market making are not crucial to back the currency.
Then we can add an insurance layer: if both market makers and trust fail, insurance company will step in and compensate.
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.
I believe it can be done using derivatives. Recently Vitalik Buterin described a way to implement trustless CFDs within Mastercoin, and people understood that it is actually superior to "escrow fund".
Something like that can be done using colored coins as well, but it is really complex and currently there are no plans to implement it.