I got it to work, here is my code and screen record.
Activities in the backstack are also changing their themes.
findPreference(getString(R.string.pref_key_night_mode)).setOnPreferenceChangeListener(new OnPreferenceChangeListener() {
        @Override
        public boolean onPreferenceChange(Preference preference, Object newValue) {
            if ((Boolean) newValue) {
                AppCompatDelegate.setDefaultNightMode(AppCompatDelegate.MODE_NIGHT_YES);
                getDelegate().setLocalNightMode(AppCompatDelegate.MODE_NIGHT_YES);
            } else {
                AppCompatDelegate.setDefaultNightMode(AppCompatDelegate.MODE_NIGHT_NO);
                getDelegate().setLocalNightMode(AppCompatDelegate.MODE_NIGHT_NO);
            }
            getDelegate().applyDayNight();
            recreate();
            return true;
        }
    });

Update
The solution above worked for Android 4.4 well, but preserved previous DayNight state in backstack on Android 7.1.
I've added manual check for night mode setting change in onResume:
@Override
protected void onResume() {
    super.onResume();
    if (mApplyNightMode) {
        mApplyNightMode = false;
        getDelegate().setLocalNightMode(PeshkaPreferences.getNightModeEnabled(this) ? AppCompatDelegate.MODE_NIGHT_YES : AppCompatDelegate.MODE_NIGHT_NO);
        getDelegate().applyDayNight();
        recreate();
    }
}
and added OnSharedPreferencesChangeListener:
protected OnSharedPreferenceChangeListener mPreferencesListener = new OnSharedPreferenceChangeListener() {
    @Override
    public void onSharedPreferenceChanged(SharedPreferences sharedPreferences, String key) {
        if (key.equals(getString(R.string.pref_key_night_mode))) {
            mApplyNightMode = true;
        }
    }
};