Galera como um anônimo acima respondeu, hoje testei e realmente funcionou em dois aparelhos Galaxy S4, o meu e da minha irmã. Sem precisar resetar o celular e excluindo definitivamente os contados google da agenda, mesmo quando vai enviar mensagem. Outro detalhe é que também exclui as fotos do Picasa sicronizadas.
Decidi escrever para deixar passo a passo como fazer:
1. Antes de mais nada desative suas conexões (Wi-Fi e Dados Móveis também)
2. Na aba contatos, vá em opções (botão das três linhas) e selecione "Contatos para exibir", deixe marcada a opção "Todos os Contatos". Esse passo é opcional, depende de quais contatos você quer que sejam exibidos.
3. Vá em Galeria > Opções> Configurações e desmarque a opção de sincronizar somente via WI-Fi.
4. Abra "Configurações", e vá até as "Contas", selecione as contas do Google (se for mais de uma) e clique em "Remover Conta"
5. Vá em Contatos e tente enviar uma mensagem, observe que ao digitara alguma letra não aparecem mais os contatos com o "g" do google do lado, ou seja, eles foram excluídos.
Mas não se preocupe que colocaremos novamente a conta no android, siga os próximos passos com bastante atenção e rigor:
6. Ative apenas uma conexão de internet (Wi-Fi ou Dados Móveis)
7. Abra novamente Configurações > Conta
8. Procure o botão Adicionar Conta > Google
9. Crie uma nova conta, ou alguma já criada por você (no meu caso preciso da conta google para usar o gmail, calendário, play store, etc)
!!!!!! Passo crítico !!!!!!
Digite o login e senha e clique "Próximo", aceite os termos clicando em OK
Obs.: deixe o celular fazer o login, que acontece muito rápido dependendo da velocidade da sua internet. Assim que mudar de tela (vai aparecer telas com opções como adicionar cartão de crédito, participar do google+ caso você não faça parte, etc), assim que a tela que você fez o login mudar, desative a conexão com a internet. FAÇA ISSO O MAIS RÁPIDO POSSÍVEL depois que fizer o login.
Isso vai gerar uma falha na sincronização da conta gmail, e você poderá trabalhar no restante das configurações com mais calma.
10. Desativada a conexão, basta seguir com a instalação/configuração da conta, escolha as opções quanto a google+, cartão de crédito etc (eu geralmente descarto)
11. Clique na conta criada. Você verá uma notificação de falha na sincronização, não se preocupe.
12. Agora basta desmarcar o que você não quer sincronizar (eu só deixo o calendário sincronizado, mas você pode desmarcar também)
Feito isso, basta religar sua conexão com a internet e... supimpa, problema resolvido.
Podem repassar esse mini tutorial, acredito que muitos usuários do Android podem até já saber disso, mas não vi nenhuma publicação que me ajudasse com todos os passos descritos, se tiverem dúvidas é só me contatar por e-mail: (lucarely2000@gmail.com) Tenho prints das telas explicando passo a passo, mas não deu pra postar aqui.
Abraço a todos e boa sorte.