Custom Block Can't Invalid the Cache
I wrote a block in Drupal 8 to render a menu based on the http headers
  of the request, which contains the users' information from the idp.


If you want to build a new page for every request then there is no point in using the page cache, so I would uninstall the core module Internal Page Cache.

Edit: Just read in drupal planet, BigPipe will be available in Drupal 8.1, then you have a perfect solution for this. But in the meantime running a site without page cache for anonymous users is fine, you still have the dynamic cache and can use the cache tags.