Apple - 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

Another way, if you also have python 3.7 in your system.
Go to the dir, where vim trying to find the python.

cd /usr/local/opt/python/Frameworks/Python.framework/Versions

And create a link to 3.7 python. Example for brew installed python:

ln -s /usr/local/Cellar/python/3.7.2/Frameworks/Python.framework/Versions/3.7/ 3.7