I've had bad luck with Debian's Ruby packages. First thing I do when I
build a new ubuntu server is pull down a fresh copy of the ruby source
from ruby-lang.org and compile it. Then I install rubygems and rails.
It seems to me that you're having more issues just trying to get up
and running with Rails than you are deploying applications, which is
an entirely different monster all together.
Here's a method of installing rails that I know from experience works
I'd get rid of all of the debian ruby/rails packages that you have
first, then use the method in the blog post I linked to. I'd install
ruby 1.8.7 instead of 1.8.6 that's mentioned in the blog though.