Language detection method "Browser" doesn't work if I check "Cache pages for anonymous users"
have you seen and tried:

https://stackoverflow.com/questions/22792062/drupal-7-always-redirecting-to-default-language


  You might be affected by a bug in Drupal core. I had the same problem
  for a while and finally found the cause and a workaround for it.
  
  It goes like this:
  
  
  Add this code to a custom module (change "mymodule" to your modules' name):

/**
 * Implements hook_language_negotiation_info_alter().
 *
 * Remove the 'cache' setting from LOCALE_LANGUAGE_NEGOTIATION_BROWSER since
 * the code that utilizes this setting will in fact prevent browser negotiation.
 */
function mymodule_language_negotiation_info_alter(&amp;$negotiation_info) {
    unset($negotiation_info[LOCALE_LANGUAGE_NEGOTIATION_BROWSER]['cache']);
}

  Clear all caches (e.g. "drush cc all")
  Go to admin/config/regional/language/configure and press "Save settings" once (this will rebuild the variable
  'language_negotiation_language').
  
  
  Now browser language detection should work properly.
  
  I'm also looking for a real solution but this requires changes in core
  and probably some discussion beforehand because of the nature of the
  bug. I've opened an issue here: Browser language detection for
  anonymous requests is broken


there is now a patch from Berdir