Just look online. I've found great places on craigslist (again, make sure you meet everyone and see the place before anything) that I stayed at for a year. Trust me, as long as you don't mind moving a bit more, you can get some great places, for cheap too.
If you're worried about leaving the other guy with all the rent, see about putting out an ad yourself. As long as it's clean when people check it out, a few won't care enough that he's normally messy and just need a place.