How do I restore libz.so.1?

The correct way to fix this problem is to download needed package by hand, then install or extract it to the system. Of course you can perform such actions from LiveCD/LiveUSB.

How to solve such problems:

  1. Visit packages.ubuntu.com.
  2. Enter missed file name in Search the contents of packages (in our case libz.so.1.2.8) specifying target Distribution (xenial in our case) and CPU Architecture (amd64):

    search options

  3. Click Search, it will show the results page:

    search results

  4. Then click on the zlib1g link

  5. In Download section click amd64:

    download <code>zlib1g</code>

  6. On opened page select nearest mirror, (copy link or download deb-file by browser)

    mirror

    wget http://mirrors.kernel.org/ubuntu/pool/main/z/zlib/zlib1g_1.2.8.dfsg-2ubuntu4_amd64.deb
    
  7. Try to install downloaded package to the system:

    sudo dpkg -i zlib1g_1.2.8.dfsg-2ubuntu4_amd64.deb
    

    If it does not work - extract it directly to filesystem:

    sudo dpkg -x zlib1g_1.2.8.dfsg-2ubuntu4_amd64.deb /
    
  8. And then for sure reinstall it with APT:

    sudo apt-get install --reinstall zlib1g
    

An extension to N0rbert's instructions, if you are doing this in a live session, make sure you are extracting the package to the root of your broken Ubuntu install, as opposed to the root of the live session itself (which won't solve anything and will disappear upon restart).

From the POV of the live session, your broken install will be mounted at something like /media/ubuntu/ae7r0-9s90s-ejf8d-d9d9f (not actual value, but some long hash similar to that). You may have to browse to it in the file explorer to get the folder to appear.

So in the live session you'd extract using a command such as the following:

sudo dpkg -x zlib1g_1.2.8.dfsg-2ubuntu4_amd64.deb /media/ubuntu/ae7r0-9s90s-ejf8d-d9d9f/

Once the missing libz.so.1 is restored to /media/ubuntu/ae7r0-9s90s-ejf8d-d9d9f/lib/x86_64-linux-gnu/, you should be able to restart, run sudo apt-get install --reinstall zlib1g in tty1, and reboot into a working system again.