Decentralised exchanges are a tough technical challenge. There is bitshares for example but it still requires a gateway such as open ledger to issue the IOUs on the blockchain.
Maybe for all coins which support lightning network functionality, so-called 'atomic swaps' might be possible - but I don't know much about technical details of this.
However i would expect decentralised exchanges to be possible on the ethereum network if you just need to trade ERC20 tokens against Ether. I think this can be trustless because the trading engine would just use smart contacts on the ethereum blockchain. I don't know if EtherDelta is decentralised, but I'm thinking something like. But I could be wrong about how possible this is.
Yeah i agree, the technical details for crypto and smart contracts are really difficult to understand. Actually I think there are really a few people in the world who really can build and understand it. But fact is that cenralised crypto exchanges feels the same as current normal bank nowadays. There will be a time we also don't need them anymore. Both centralized banks and crypto exchanges.