Homebrew Vim with Python support depends on Python 3.7.0, and I have to use 3.6.5
To solve this with homebrew, you can temporarily backdate homebrew-core and set the HOMEBREW_NO_AUTO_UPDATE variable to hold it in place:

cd `brew --repo homebrew/core`
git checkout f2a764ef944b1080be64bd88dca9a1d80130c558
export HOMEBREW_NO_AUTO_UPDATE=1
brew install python
brew install vim --with-python


I don't recommend permanently backdating homebrew-core, as you will miss out on security patches, but it is useful for testing purposes.

A more robust approach, would be to use pyenv as suggested in the comment by @Dustin Wheeler. You can also extract old versions of homebrew formulae into your own tap (tap_owner/tap_name) using the brew extract command:

brew extract python tap_owner/tap_name --version=3.6.5