Você pode usar o módulo apt python, mas ele só verifica se o pacote está instalado. Ele falhará nas distribuições não-deb ou, se instalado fora do gerenciador de pacotes:
import apt
cache = apt.Cache()
cache.open()
cache["git-core"].is_installed# Evaluates true if git is installed
Tente executar o git e lidar com a exceção se ela falhar:
import subprocess
try:
# pipe output to /dev/null for silence
null = open("/dev/null", "w")
subprocess.Popen("git", stdout=null, stderr=null)
null.close()
except OSError:
print("git not found")
Uma terceira opção seria testar todos os caminhos em $PATH
e testar se você tem permissão de execução no caminho / git.