O Python não é necessário, e é fácil de provar: uma instalação básica do Debian pode entrar na rede, etc., mas não tem Python.
Python é um intérprete como qualquer outro. Pode ser necessário em algumas distribuições, se suas ferramentas principais (gerenciadores de pacotes, etc.) forem escritas em Python; outros intérpretes são necessários sem que ninguém faça barulho (Perl, por exemplo, ou um shell no estilo POSIX). Como o Python é muito usado hoje em dia, muitas distribuições o instalam por padrão em sua configuração padrão, mesmo que não exijam absolutamente isso.
No que diz respeito ao Android, você precisa do Python para criá-lo e executar algumas das ferramentas de desenvolvimento (começando com Repo ). O sistema operacional Android, conforme executado nos dispositivos de destino, não inclui o Python.