Composer says Git not found

You should install git first

apt-get install git

Using --prefer-dist worked:

composer install --prefer-dist

to force dist part, which @ivoba mentioned; it seems default switch which uses git is --prefer-source.