Homebrew refuses to work on macOS Sierra
For the big picture: I solved the issue by uninstalling homebrew and then re-installing it again. In order to help people maybe gain a bit more insight, let me go into further detail.

Researching the Internet for the error message, my first hunch was that it had something to do with permissions. Check a discussion on Reddit or on the Homebrew GitHub for reference. However, running sudo chown -R $(whoami) /usr/local did not to the trick. In any way, I would advise to be very careful using this command as it will transfer the ownership of /usr/local from the root user to yourself, which, apparently, was not intended by Apple. You can undo this by running

sudo chmod 0755 /usr/local
sudo chown root:wheel /usr/local


However, note that this will only undo it for the folder /usr/local and not recursively for all its files.

So, I was left with uninstalling. If you want to do the same, type

ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/uninstall)"


in order to run the official script or see the Homebrew FAQ for reference.
Be aware that this will also uninstall all your Formulae and that you will be left with installing them manually again later on.

To re-install homebrew, simply run

/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"


If anyone figures out why I got the error in the first place or how it can  be addressed directly, please let me know.