I had to install the Command Line Tools in the latest Xcode-Version (4.3.1) and
sudo gem install rails
worked like a charm.
To install Command Line Tools, go to Xcode Preferences > Downloads or use the following command in terminal (thx @Purell):
xcode-select --install