I've been toying with the idea of a computation-backed currency. Any computer can obviously pay another computer in computer time. This means that any node in the system can issue currency backed by computer time. This would require trust, but it would be trust between neighbors rather than trust in one central exchange.
The problem is that that's not really a currency. It's zillions of IOUs. I don't know how to make transactions between two nodes that don't trust each other or how to come up with one number for someone's net worth.