If you install Xcode, within Xcode preferences in the Download pane you can have it download and install the command line tools for you. Works perfectly.

After that homebrew works without any issues.