How to fix homebrew permissions?

As a first option to whomever lands here like I did, follow whatever this suggests you to do:

brew doctor

It's the safest path, and amongst other things, it suggested me to:

sudo chown -R $(whoami) /usr/local

which solved that permissions issue.

The OP did just that but apparently didn't get the above suggestion; you might, and it's always better to start there, and only then look for non trivial solutions if it didn't help.

If you're on OSX High Sierra, /usr/local can no longer be chown'd. You can use:

sudo chown -R $(whoami) $(brew --prefix)/*

I was able to solve the problem by using chown on the folder:

sudo chown -R "$USER":admin /usr/local

Also you'll (most probably) have to do the same on /Library/Caches/Homebrew:

sudo chown -R "$USER":admin /Library/Caches/Homebrew

Apparently I had used sudo before in a way that altered my folder permission on /usr/local, from here on forward all installations with brew have proven to be successful.

This answer comes courtesy of gitHub's homebrew issue tracker

New command for users on macOS High Sierra as it is not possible to chown on /usr/local:

bash/zsh:

sudo chown -R $(whoami) $(brew --prefix)/*

fish:

sudo chown -R (whoami) (brew --prefix)/*

Reference: Can't chown /usr/local in High Sierra