First, a prepaid sim will only work if you've unlocked your Iphone 4. That goes for any GSM phone. And the only way to unlock it without getting the unlock code from AT&T, which they likely will not give you, is to jail brake your Iphone and then unlock it.

I found this company http://www.onesimcard.com/ based on a comparison of sim card companies that someone in one of the travel forums on this site produced. They do sell the microsim for Iphone 4. One Sim has the best deals out of all of the sites I checked. The reviews are pretty good. At onesim coverage is provided by SRF or Orange. You should have coverage throughout your trip around Paris.

I was going to get a pre paid sim for my trip in July but after thinking about it, the cost to use data is, while cheaper with a onesim card still too cost prohibitive even when checking FB, Twitter or getting email. It takes a lot of megabytes to load FB or HTML email. If you must check email set it so that you have to check it manually.