Keep in mind they don't say they won't collect and store the information. They just won't use it to customize your ads. They are still collecting the information and will find other ways to use it.

Also, opting out of the ads doesn't opt out of the data collection. The problem is the privacy violation; once they do that, I guess targeted ads are better than untargeted ones. (Or do they mean that they won't share my data with advertisers if I opt out?)

You can opt out of FB ads without having an account via http://optout.aboutads.info.

Not sure why their site only sometimes shows this link :/.

That requires me to enable 3rd party cookies.

The type of ads you see on FB is only relevant to FB users.

Facebook also has the audience network, which serves ads on other websites and apps.

Then I seem not to understand the benefit they see from tracking non-users' information - how can this be of benefit to advertisers if these users are never targeted? In particular, what benefits would be generated by linking this tracking information with the real identify of a non-FB user (that couldn't also be leveraged in a semi-anonymous way)?

In other words, I see the benefit to FB of being able to say "Person A likes 1, 2, 3; User B likes 1 and 2 - perhaps they also like 3?" where A is a non-user and B is a FB user, but I don't see the benefit derived from identifying Person A to advertisers if they can only target that person on FB, where they aren't a user?

They don't allow advertisers to target non-users. I'm sure they use non-user data for clustering, just as you described.

They also probably use it when the user finally does create a FB account.