OK, I've figured it out:

In order to get the installation of Composer, and subsequently Drush, to work, zip and unzip extensions needs to be installed:

$ apt-get update
$ apt-get install zip unzip

Then it's pretty plain sailing installing Composer. Make sure you have installed proper version of Curl first:

$ apt-get install curl php7-cli git

Then:
$ curl -sS https://getcomposer.org/installer | sudo php -- --install-dir=/usr/local/bin --filename=composer

And Drush:

$ composer global require drush/drush

Then use Composer to create your project. If you run into permission issues, then:

1. Add "www" group and add your user to this group:
   $ sudo groupadd www
   $ sudo usermod -a -G www [user]

2. logout/login

3. Set ownership and write permissions:
   $ sudo chown -R root:www /var/www
   $ sudo chmod 2775 /var/www
   $ find /var/www -type d -exec sudo chmod 2775 {} +
   $ find /var/www -type f -exec sudo chmod 0664 {} +

Also note, you cannot run Composer on the smallest server config. It's fairly memory hungry, so min. 1GB is recommended.