With Xcode 4.6 I was also getting this problem. I installed the command line tools which made gcc available in /usr/bin/gcc.

I managed to get it to work using:

rvm install 1.9.3 --with-gcc=gcc

NB. I dont have homebrew installed.

via compiler errors – Cannot compile ruby 1.9.3 – Stack Overflow.