Insuring bitcoins is actually pretty easy. As a sidenote, there are already people doing it. The ideal way to do it would be to audit the exchange, and possibly also use an escrow, populated with money from the exchange, that pays you (the insurer) if the exchange loses money. It would be in the interest of the exchange to cooperate in these areas, in order to promote the availability of cheaper insurance, and therefore more customers.
A digression: Bitcoin would be the government regulator's wet dream if you could assign people addresses (and they could only use the assigned address), because you can trivially track all transactions. Actually, I have in mind a way to implement such a system in a (likely) cryptographically sound and enforceable way. But in theory, the government could outlaw cash and track all transactions anyway.