Um método simplesmente usa agregação condicional:
insert into users_settings (user_id, key)
select user_id, 'app_reminder'
from users_settings
group by user_id
having sum(key = 'app_reminder') = 0;
Você pode querer uma solução mais genérica. Se você quiser garantir que os pares de usuário/chave nunca sejam duplicados, crie uma restrição ou índice exclusivo nessas colunas:
alter table users_settings add constraint unq_users_settings_user_id_key
unique (user_id, key);
Em seguida, você pode pular a inserção das linhas usando
on duplicate key update :insert into users_settings (user_id, key)
select distinct user_id, 'app_reminder'
from users_settings
on duplicate key update user_id = values(user_id);
A
update não faz nada, pois o valor é o mesmo. O MySQL pula a inserção e não retorna um erro. 
