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.