I worked out a solution that did not involve CDI.
I set the locale after the restore view phase of the JSF life cycle. 
@SuppressWarnings("serial")
public class LifeCycleListener implements PhaseListener {
  ...
  public void afterPhase(PhaseEvent event) {
    if (event.getPhaseId() == PhaseId.RESTORE_VIEW) {
      // let's try first to get the language from the request parameter  
      // and if it is a supported language then put it to session
      String reqParamLang = FacesContext.getCurrentInstance().getExternalContext().getRequestParameterMap().get("lang");
      if (reqParamLang != null) {
        Iterator<Locale> localeIterator = FacesContext.getCurrentInstance().getApplication().getSupportedLocales();
        while (localeIterator.hasNext()) {
          Locale locale = localeIterator.next();
          if (reqParamLang.equals(locale.toString())) {
            FacesContext.getCurrentInstance().getExternalContext().getSessionMap().put("lang", reqParamLang);
            Logger.getLogger(this.getClass().getName()).info("will change locale to " + locale);
          }
        }
      } 
      // get the language from the session and if available then set the locale 
      String sessionLang = (String) FacesContext.getCurrentInstance().getExternalContext().getSessionMap().get("lang");
      if (sessionLang != null) {
          FacesContext.getCurrentInstance().getViewRoot().setLocale(new Locale(sessionLang));
      }
    }
  }
}