When using VaryByCustom for caching, you have access to the whole Request object and you can get the headers from there and create your own cache key based on your requirement.
public override string GetVaryByCustomString(HttpContext context, string arg)
{
// Do something with Request.Headers["Accept-Encoding"] (like checking if gzip is preferred...)
return "custom-encoding-key";
}