Ultimately I think mining protects against sybil attacks and thus helps everyone agree on a single transaction history. Without mining, it would be fairly easy to create multiple alternate histories and it would be hard to tell which one to believe.

(If you don't care about sybils, you can use Ripple which requires no mining.)