Think smaller. They don't need to consider billion users at once, for modeling you can start with hundreds of thousands or few million. Trillion pieces of metadata can be reduced to tens of thousands of features (eg. instead of feeding in the raw status updates, assign each update to some class, put in some mood measurement etc). This reduction does not need to be fully automated, it can be human assisted (humans coming up with ideas on what kind of features to extract). Instead of considering all possible ads, you can start by taking out the long tail of ads with very little interaction data and focus on some specific categories.

Building this kind of predictive models is not black magic. This is what companies do to figure out who they should target on direct marketing campaigns. Applying some magical deep learning dust can quite likely improve the results (in Facebook scale), but it's not mandatory. Computationally the hardest part is building the models. Once they are done, applying them to millions and millions of customers is more straight forward.

When considering what is possible, you need to also consider the stakes. Facebook ad revenue is something like $10 billion per quarter[1]. To make more money, I can think of three ways: add more users, make users spend more time looking at their feed or make more money per ad slot. Better targeting means more money per ad slot since some customers are paying directly based on the clicks. Since improvements lead to better revenue, extra hardware costs are easy to justify.

[1] http://www.adweek.com/digital/facebook-raked-in-9-16-billion...