Значит, алгоритм такой:
При загрузке index.php читаем сессию, если там есть user_id, идем в базу и переписываем оттуда инфу о пользователе (в т.ч. язык) в куку, если user_id нет, читаем куку, если там нет языка, то берем его из Accept-Language и записываем язык оттуда в куку. Т.е. в куке теперь всегда есть нужный язык.
Далее при запросах к action.php (который выдает контент) берем язык из куки и на основании его отправляем данные. Все хорошо, но смущает, что при каждой отправке будет производится дополнительный опрос куки, что не очень быстро. Может быть делать для гостей краткосрочное хранилище на сервере, типа второй сессии?