As Andrew has suggested it's probably best if you try to rent privately. The website leboncoin.fr is the best place to start looking. When I first came to France 8 years ago I got around the issue of the correct dossier by offering to pay 6 or 12 months rent up front. After that the landlord was prepared to accept rent on a monthly basis. However, I've heard that landlords are much more cautious these days and may ask for references and (French) guarantors etc. I guess you will just have to contact lots of landlords and see what they say. Hopefully, your French is up to it! If you have decided to move here then setting up a French bank account is a must anyway so you should probably just do it.
Best of luck and I hope it goes well for you.
Exellent choice - far better to rent if you don't know where you want to be, it also helps avoid making very costly mistakes and allows you to see what an area is like year round. As for the french rental market - most houses for rent are unfurnished - that's the standard thing - pick an area and have a look on leboncoin. I've rented several times using it - saves paying agents (and most agents won't even bother with you as you're non-standard and won't be able to put a dossier together) - but your frenhc will need to be up to speed and you'll need to convince owners of your solvability which maybe difficult as you don't fit into any frenhc boxes. You'll definitely need a french bank account, but then again you'll need one what ever you do here! Hope that helps a bit ;-)