The new idea that caught my eye here: Facebook could hire a firm to audit their privacy processes. They wouldn't have to give up any flexibility in their privacy policy updating practices, the review could just be of their processes, and it would provide some reassurance.
This is also the sort of thing where if one leader did it (Google, Twitter, etc.), it could basically force the others to follow.