I here about the impossability of renting apartments (by foreigners) here all the time. But in my experience (I am on my third apartment, the last two 1 year contracts) it isn't always so. Some landlords are thick headed and want to to do it the way they always did it. But in my three cases I wasn't even asked for a garantie, much less provided one. A few letters of reference (got you bank to just something saying you have a good credit and have an average of $xxxx put into your account each month) seem to work wonders here.
And if the landlord gives you a hard time, tell him/her to piss off. There are lots of apartments out there and some landlords are cool. All three of mine have been amazingly agreeable. Far more than I ever recall in Canada, the US, France or Africa.