Note that linking as in @Davids post will interfere with your build tools and link into your OS (which is most likely not what you want if you're using brew), but you can just execute each command above except omit the 'brew link' lines and everything will still build just fine, eg:
gem uninstall nokogiri libxml-ruby
brew update
brew uninstall libxml2
brew install libxml2 --with-xml2-config
brew install libxslt
gem install nokogiri -- --with-xml2-include=/usr/local/Cellar/libxml2/2.8.0/include/libxml2/ --with-xml2-lib=/usr/local/Cellar/libxml2/2.8.0/lib/ --with-xslt-dir=/usr/local/Cellar/libxslt/1.1.26/