Macos – Can’t reinstall or uninstall Homebrew after blowing away contents of /usr/local/bin

I removed ALL content from /usr/local/bin folder (including 'brew'). Homebrew isn't working anymore and I seem to be stuck in a limbo. When I try to install it says:

It appears Homebrew is already installed. If your intent is to
reinstall you should do the following before running this installer
again:
ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/uninstall)"

When I run the given uninstall command it says:

Failed to locate Homebrew!

Background

The problem arose when I attempted to remove node.js by following this guide:
https://stackoverflow.com/a/11178106/1736012

To completely uninstall node + npm is to do the following:

1. go to /usr/local/lib and delete any node and node_modules
2. go to /usr/local/include and delete any node and node_modules directory
3. if you installed with brew install node, then run brew uninstall node in your terminal
4. check your Home directory for any local or lib or
   include folders, and delete any node or node_modules from there
5. go to /usr/local/bin and delete any node executable

Especially 5 was bad! That's what led me to remove everything under /usr/local/bin. So brew doctor won't work (brew isn't recognized anymore). Brew worked fine before this.

What I tried

This does not work either as brew is missing:

rm -rf /usr/local/Cellar /usr/local/.git && brew cleanup
ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install )"

I tried various scripts like this one for example: https://apple.stackexchange.com/a/85481. And this: https://gist.github.com/SteveBenner/11254428. None of them is working (both assumes that brew command is there)…

What can I do to re install Homebrew so that it works as before??