Edit: As of , this post is out of date. Please see here for updated instructions.
A while back it was decided that X11 support would be removed from homebrew-core. Taking matters into my own hands and in the spirit of OSS, I now maintain my own version for anyone who wants it. On MacOS, you will find homebrew-core in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core.
Once you have the fork brew reinstall emacs --with-x11.
I only occasionally maintain that branch so if you want something more up-to-date, be sure to rebase against homebrew-core/master.
Enjoy!