I think you're overselling how much Google cares (or needs to care) about trust.
They dominate search traffic (in the markets/countries they exist for). Businesses don't use AdWords because they "trust" Google. They suffer through using AdWords because it's the only game in town.
A lot of people probably see more Facebook ads than Google ones. And Facebook knows a lot about users, probably including some things that Google knows less reliably. The relevant problem is, do they seem any less scummy?
They dominate search traffic (in the markets/countries they exist for). Businesses don't use AdWords because they "trust" Google. They suffer through using AdWords because it's the only game in town.