This is what I had to do to build and install Neovim 0.3.4 with Python2 and Python3 support on Debian Stretch.
$ sudo apt install cmake libuv1-dev libmsgpack-dev libluajit-5.1-dev libunibilium-dev libtermkey-dev libvterm-dev libjemalloc-dev luajit lua-mpack gperf python3-pip
$ sudo pip2 install --upgrade pynvim
$ sudo pip3 install --upgrade pynvim
$ git clone neovim/neovim