Bueno, esta tarde he estado instalando Rails en Debian y me he encontrado en que habian varios errores en los que bash no detectaba mvc, otro en el que al tener ruby 1.9 (apt-get install ruby-full) rails no era compatible y todo el tema. Asi que os dejo, la forma en la que lo he solucionado yo, ya que no me extrañaria que alguien tuviera problemas similares:

sudo apt-get update

sudo apt-get install git-core curl zlib1g-dev build-essential libssl-dev libreadline-dev libyaml-dev libsqlite3-dev sqlite3 libxml2-dev libxslt1-dev libcurl4-openssl-dev python-software-properties libffi-dev

cd

git clone git://github.com/sstephenson/rbenv.git .rbenv

echo 'export PATH="$HOME/.rbenv/bin:$PATH"' >> ~/.bashrc

echo 'eval "$(rbenv init -)"' >> ~/.bashrc

exec $SHELL

git clone git://github.com/sstephenson/ruby-build.git ~/.rbenv/plugins/ruby-build

echo 'export PATH="$HOME/.rbenv/plugins/ruby-build/bin:$PATH"' >> ~/.bashrc

exec $SHELL

git clone https://github.com/sstephenson/rbenv-gem-rehash.git ~/.rbenv/plugins/rbenv-gem-rehash

rbenv install 2.2.3

rbenv global 2.2.3

ruby -v

curl -sL https://deb.nodesource.com/setup_4.x | sudo -E bash -

sudo apt-get install -y nodejs

apt install sqlite3 libsqlite3-dev

apt install zlibc zlib1g-dev libxml2 libxml2-dev libxslt1.1 libxslt1-dev

gem install bundler

gem install rails --pre

Y ya estaria todo funcional para ejecutar rails new App

Saludos