Exchanges are already "decentralized". There has got to be at least a half-dozen decent exchanges. They can be started by pretty much anyone, anywhere, at any time. If you don't like or trust current exchanges, you can start your own and show everyone how it's done, or if you don't like that, you can exchange directly person to person.
There is some truth in this perspective, but it does miss an important distinction. There is value in centralization for exchange; (let's not forget that currency itself is an example of exactly this centralization) it's faster, it's cheaper, it's more liquid. So people naturally gravitate to a smaller number of highly liquid marketplaces. On the other hand, this creates tremendous risk *specifically* because Bitcoin is digital cash. If it is stolen, it is stolen irretrievably, and within minutes. Consider the equivalent scenario with banknotes or gold, and you can see such an opportunity is rare in the modern world.
A central store of wealth like that, even if there's 5 of them in the world rather than 1, is a magnet not only for hackers (certainly that's a huge risk) but also for political actors; see Liberty Reserve and e-gold for good examples.
There is trust involved with exchanges, but I don't see why I should care. When I buy something from Amazon I need to trust them. I don't lose sleep at night wondering if Amazon is going to run away with my money.
You don't give Amazon cash. Bitcoin is digital cash. Of course, Amazon is not the best example to make my point; but you feel comfortable online shopping with smaller businesses mainly because you are not sending cash thousands of miles away with no recourse. Similarly, crime/hacking against Amazon is greatly limited by the fact that it isn't holding cash on its servers.
In order to make an exchange that achieves decentralized trust-free consensus you'd have to build a program that is similar to Bitcoin and then only currencies that rigidly follow certain design patterns would be allowed to be traded on the platform (Fiat never works), and then at the end of the day it would be much more expensive and slow to use than a traditional centralized exchange.
Another solution looking for a problem...
As stated above, crypto-crypto decentralized exchange already exists in various forms. Not a very hard problem to solve, once you've figured out Bitcoin. More expensive/slow? Generally yes, but it can still offer advantages as discussed. As for fiat being impossible to do decentralised, well, it's discussed above, but solutions that are less than perfect do exist, and I argue, are worth looking into.