So as @NicolasMiari mentioned in a comment above, the fix to my issue ended up having to have both Xcode 7 and Xcode 8 on my machine. I went on the apple developer site, downloaded Xcode 8, saved it to my documents and then used:
sudo xcode-select -switch ~/Documents/Xcode.app/
and then ran my brew install which worked as expected. Afterwards I ran:
sudo xcode-select -switch /Applications/Xcode.app/
to switch back to Xcode 7.3.1.
Hope this helps someone else, and thanks for the suggestions.