I was in the same situation once upon a time.
French banks can initially refuse your business, but if you cannot find a bank then you can go to the Banque de France and ask them to assign you a bank. (as Gagravarr suggested) They will pick one for you and that bank would then have to give you an account, free of charge, with no-charge basic services. (bank card, so you can withdraw money from their bank machines and a chequebook). Expect the assigned bank to look down their nose at you. Prepare a few polite but pointed remarks about your rights if they give you a hassle. They have three days to open the account for you.
The law in question is articles D312-5 and D312-6 of the Code Monétaire et Financier. The only requirement is that you are a resident.
When you go to the Banque de France you'll need:
- Proof of residency (carte de séjour/nationalité)
- Proof you live somewhere, the famous "justicatif de domicile", which is usually a telephone or electricity bill no more than three months old. Other documents are acceptable, you could call the BdF and ask before going there.
- An "attestation de refus", a document from a bank that says they won't give you an account. The BdF wants proof that you at least tried.
- to fill out their request form, which is quite straightforward.
Go see www.banque-france.fr and look up "droit au compte," probably under the "particuliers" somewhere, to get more details and a copy of their request form.
Having said that I just went to La Poste (now le Banque Postale), which once upon a time was the government banque for people. They gave me an real account, and with a smile and no hassle. And I was "fresh off the boat," so to speak. So I didn't have to go through the BdF.