In Cuba I found a lot of places that offered all of the above, but they're a special case where you need a license to rent to foreigners. That's a good idea about getting a house and then contracting out for work.
How do you deal with trust in those cases?
Trust is tough cause in one case I had rented a room which included a separate kitchen and bathroom/shower (reasonable for the price I was paying, $150). Well, the renter put another person in my room at one point, charging that person the same as me and therefore making double on the same space. In another case, the renter told me I didn't prepay him at the start of the month (something I swear I did) and I had no proof that I did so I ended up probably paying twice ($90 rent, so…). In both cases, I moved out soon after.
The lesson being that sometimes you're going to get worked over (because you're a foreigner) and you just have to take it in stride and move on. The important thing is to be clear, to get written and signed receipts if need be, and to learn to say no if things start to sound fishy or not close to what you expected. Also don't pay ahead, try to keep everything current so that if you do need to move somewhere else, you won't be out of luck because you decided to make things easy and just pay a few months in advance.
That's the benefit of doing the hostel thing and talking with people that have been where you're going. Some will say what's in your LP and some might have other suggestions. The staff as well -- they might have friends in another city or tell you where they stay, bc it's cheaper for them, and maybe hook you up.
There's also the AirBnB w/o paying: couchsurfing.org - which has been around a while.
personlurking mentioned Portugal - it's been a while but when I was in the Algarve during a summer trip there tended to be some little old ladies always letting their places out. They looked quite nice and, if you were staying a week or more, were reasonably priced. Even better if you find some companions.