nokogiri

# using rvm with ruby-1.8.7-p249

# latest version 2.7.7 2010-06-17
brew install libxml2

# installing libxslt from source code
wget ftp://xmlsoft.org/libxml2/libxslt-1.1.26.tar.gz
tar xvfz libxslt-1.1.26.tar.gz
cd libxslt-1.1.26
./configure --prefix=/usr/local/Cellar/libxslt/1.1.26 --with-libxml-prefix=/usr/local/Cellar/libxml2/2.7.7
make
sudo make install

# installing nokogiri with this new compiled libs
gem install nokogiri -- --with-xml2-include=/usr/local/Cellar/libxml2/2.7.7/include/libxml2 --with-xml2-lib=/usr/local/Cellar/libxml2/2.7.7/lib --with-xslt-dir=/usr/local/Cellar/libxslt/1.1.26

As a self-contained solution, I wrote a Ruby script that just installs Nokogiri using Homebrew's libraries instead of Apple's. It seems to flawlessly solve the issue on normal systems; I've used it twice without any issues. You can choose whether to install using either RubyGems or Bundler. Contributions or suggestions are welcome!

I can confirm xcode-select --install worked for me. Thanks @arojoal