Por que é impossível desinstalar completamente o Facebook de todos os telefones Android?

Não é impossível.

É difícil porque muitas vezes é um aplicativo incluído no sistema operacional do dispositivo. É semelhante a como o Windows como Notepad, Internet Explorer, e uma série de outros programas.

Se você não é um usuário do Facebook, basta ir na gaveta do seu aplicativo ou lista de aplicativos e remover as atualizações e depois desabilitá-lo. Isso não vai se livrar dele, mas sim torná-lo super pequeno e dormente até o momento em que você ativá-lo (e atualizá-lo) novamente. Dependendo da skin que você tem no seu dispositivo, você também pode optar por ocultar o aplicativo

Para se livrar completamente do aplicativo e de qualquer outro aplicativo que você não quer no seu dispositivo, você terá que root o dispositivo Android. Uma vez enraizado e você tem acesso root, há um número de aplicativos que você pode instalar (se não estiver incluído com seu software de enraizamento) que pode se livrar completamente do aplicativo do Facebook.

Pessoalmente, eu aconselho que você simplesmente remova as atualizações e depois desabilite o aplicativo. Se a memória servir, os restos deixados para trás são cerca de 50MB, o que é muito pouco espaço. Se você está entrando em um tumulto sobre isso, você tem problemas muito maiores.