I am also an international student going to Minneapolis and I suggest you try finding housing before August. I can't say my search is successful as yet but I am fairly certain I'll find something before I get there. You should send out an email to your department and ask them to forward it to current and incoming students. There a bound to be a few people looking for housing/housemates. And if you do find someone all you need to do is schedule a few skype calls to ensure you are compatible. Also, you could start looking at craigslist and responding to listings. Things will really open up in the May-June period. The cities forum on gradcafe has tons of useful information on the best neighbourhoods for grad students and on what a decent rental budget looks like.
It is definitely stressful, it's seems doable!
By the way, if all else fails, the university does provide cheap temporary housing for international students. However, one would have to be prepared to settle for a less that satisfactory place in august since all the good stuff might have dried up. Also, finding a roommate in august might be tough.