I think that the Step 1 you offered is a really good idea.
Only option that I have came up with to keep things honest around fiat is a self-regulatory information based system. The exchanges have to pass quarterly audits to show that all the fiat is there and it isn't being used for anything else that it is meant to. These audits will be voluntary of course, but those exchanges who refuse cooperation will be flagged untrustworthy in the wider field of information around bitcoin. This will cause a problem of neutrality, but I think that this can be overcome with proper methods.
I think that using information to promote some exchanges and warn people about other exchanges is the only realistic regulatory system that doesn't have to involve the state. And the good thing is that it also works globally, while state enforced regulations only work locally.