Where do I add a new cache context for an entity?
You should indeed use hook_entity_build_defaults_alter(). Its documentation even explicitly states this:


  Alter entity renderable values before cache checking in drupal_render().
  
  The values in the #cache key of the renderable array are used to determine if a cache entry exists for the entity's rendered output. Ideally only values that pertain to caching should be altered in this hook.


It probably didn't work for you because you forgot to clear the render cache after implementing that hook.

That hook is invoked in https://api.drupal.org/api/drupal/core%21lib%21Drupal%21Core%21Entity%21EntityViewBuilder.php/class/EntityViewBuilder/8

Also see https://www.drupal.org/developing/api/8/cache/contexts for an overview of cache contexts (what they are, how to use them, which ones core ships with).