The Trellis README mentions that it configures a server with Ubuntu 14.04. Could you check that your droplet is running 14.04?
There is progress toward moving to 16.04 soon. But if you try to provision a 16.04 droplet currently, you will likely get the error in your output above: /usr/bin/python: not found.