use AWS EC2, I regularly rent out 15 core machine with 32GB ram for 1$ per hour, you can try getting an instance in a spot market which 20-3% cheaper (though you need to be careful).
REST API and Streaming API are like apples and oranges, a lot of things just cant be done with the streaming api.Esp. accessing past tweets, search results, social network etc.
A good thing about twitter was that their social network was more open than the facebook's social network, with newer rate limits its going to be really difficult to crawl it.