I worked with Travis to get the cache flag on my personal repo for testing, and I'm happy to report that all works great (after a day of churning builds).
For some background: Travis has enabled caching for their new infrastructure, but the feature is brand new and not yet generally available. For now it requires a special flag (set on their end) on your repo. Once they're satisfied with its stability, the flag will be granted to everyone. Note that the flag comes with the caveat of invalidating all current caches. That's not a problem for us, other than slowing things down for a few hours. I was primarily worried about unintended side-effects of opting in, so I added it on my own repo for testing before requesting it here.
If there's no reason to delay our move, I'll request the flag for this repo tomorrow (4/21).
Once that's take care of, we can merge this for Trusty goodness. On the day that Xenial is scheduled to be released :p.
Next step is c++11, which should be painless to enable now.
Note that this includes #7792, otherwise the OSX build fails. @laanwj I'm happy to rebase if you'd prefer to merge that first.