I think caching can work, but at a different level of granularity. Rather than cache a person's full timeline, which is composed of multiple sub-feeds (each of which requires a database query), cache the data from the sub-feeds themselves, then recombine them on every page load. This would significantly lower the number of database queries, as each cache element would be invalidated only when its "owner" sends a tweet. This solution would be much more CPU intensive on the application servers, though, and Ruby may not be the best tool for the job if that were the case.
I really hope my initial post wasn't interpreted the way it was to validate that response. I don't take back anything I said--and I'm sure it's not what I want to hear. Architectures scale, not languages... Twitter simply cannot be distributed... it's not news, I've written about it earlier.