I had the EXACT same problem as you did until I really got a hold of understanding what MVC really meant.
I thought I understood it (yea, model, view, controller, gottit, so what). I figured it was about as important as a folder for css and a folder for scripts. But MVC is the core structure of how rails operates, so it is super important.
A friend of mine who is a rails developer helped me immensely by describing MVC as
Model - Anything that describes the structure of your data and interacts with the database
View - The layout and display of the page
Controller - gets the data from the model and passes it to the view.
I didn't bother with a 'restful' gem, as rail3 (which I decided to learn with) is already restful, so I'm not sure what that gem would have done for you. But it is true, some Gems won't work, I think that is just the way things are with Rails and Python due to different versions, and they being younger languages (though this can happen with PHP packages also I think, I never really used many of them).
I also dove in head first and went with MongoDB with MongoMapper, which I wanted to learn anyway, instead of using mysql and ActiveRecord.
The railscasts are actually quite good, though I actually learned by creating a twitter clone
http://teachmetocode.com/screencasts/creating-a-twitter-clon...
The tutorial wasn't flawless, but I am using MongoDB and Rails3, so I wasn't expecting it to work perfectly, but I eventually got it all working.
Part of my challenge with Ruby was that it seemed to do SO much for me that I didn't understand what it was doing, but it kinda worked. Then when I wanted to make changes, I didn't know enough about what it was doing to get it to work.
As far as Heroku, I'm yet to actually release a rails app, so I haven't even tried that. I decided to learn Rails because it seemed like every developer I've teamed up with over the past year has been a ruby dev person, and I figured it's easier for me to learn their language and add to my quiver than get them programming in PHP which some of them knew, but didn't really like.
After using Ruby, I can't say that I'm a complete convert, as I think I could still get much done in PHP at about the same pace, but I think we're moving into a rails world.
MVC does make sense when you get used to it.
Best of luck.