deoplete.nvimを使いたかったのでrequirementsを満たす必要がありました。
Amazon Linuxで試したときの手順です。

pyenvとvimのソースを取得するためにgitをインストールする

$ sudo yum install -y git

pyenvをインストールしてbashの設定を変更する

$ git clone https://github.com/pyenv/pyenv.git ~/.pyenv
$ echo 'export PYENV_ROOT="$HOME/.pyenv"' >> ~/.bash_profile
$ echo 'export PATH="$PYENV_ROOT/bin:$PATH"' >> ~/.bash_profile
$ echo 'eval "$(pyenv init -)"' >> ~/.bash_profile
$ source ~/.bash_profile

python2と3をpyenvでインストールする

$ sudo yum install -y readline-devel bzip2-devel openssl-devel sqlite-devel patch gcc
$ CONFIGURE_OPTS="--enable-shared" pyenv install 3.6.6
$ CONFIGURE_OPTS="--enable-shared" pyenv install 2.7.9
$ pyenv global 2.7.9 3.6.6
$ pyenv rehash

pythonのライブラリをVimと共有するために--enable-sharedオプションが必要です。

Pythonのneovim用クライアントとgreenletをインストールする

$ pip3 install neovim
$ pip3 uninstall -y greenlet
$ pip3 install greenlet --no-binary :all:

neovimの依存関係でついてくるgreenletをpip3で普通にインストールするとどうやら非互換のバイナリファイルが含まれてしまうみたいだったので--no-binary :all:オプションを付けて再インストールします。

vimをソースコードからインストールする

今回はユーザーのホームディレクトリ以下にインストールしました。

$ mkdir -p ~/local/src
$ git clone --depth 1 https://github.com/vim/vim ~/local/src/vim
$ cd ~/local/src/vim/src
$ LDFLAGS="-Wl,-rpath=${HOME}/.pyenv/versions/2.7.9/lib:${HOME}/.pyenv/versions/3.6.6/lib"   ./configure --prefix=$HOME/local/vim --enable-luainterp=yes --enable-python3interp=yes --enable-pythoninterp=yes --enable-gui=no --enable-multibyte
$ make
$ make install
$ echo 'export PATH="$HOME/local/vim/bin:$PATH"' >> ~/.bashrc
$ source ~/.bashrc
$ vim --version

pythonのライブラリとリンクするためにvimをLDFLAGS変数付きでインストールしました。

以上です。

本記事の英語版