I have been trying to install GCC using Homebrew but I keep encoutering the following error:

Error: gcc: the bottle needs the Apple Command Line Tools to be installed.
  You can install them, if desired, with:
    xcode-select --install

The real problem is that I have already installed, and even uninstalled and reinstalled Xcode command line tools.