Certificat de célibat/coutume

[Nancy]

сертификат, то что я сейчас не замужем может выдать только посольство России во Франции?

Да. Туда нужен Ваш российский паспорт, Ваш загран, плюс св-во о разводе если таковой был..

недостаточно заверенной нотариусом справки?

Иногда бывает достаточно - зависит от конкретной мэрии.

у меня фамилия девичья (я получила новый паспорт) для мерии какие документы нужны

Такие, какие Вам скажет ваш будущий супруг - именно он узнает все в своей мэрии. Обычно это св-во о рождении с апостилем, переведенное на французский, плюс справка о месте Вашего жительства, плюс все еще иногда - медицинский сертификат (certificat medical), который вроде отменили, но некоторые мэрии его все равно требуют.

как долго ждать регистрацию мерии?

Этап первый - узнаете, какие документы нужны. Этап второй - готовите все документы (апостили, переводы, справки). Этап третий - подаете все в мэрию, либо лично, либо по почте отсылаете жениху. Тогда же можно назначить дату бракосочетания (зависит от мэрии, когда у них есть свободные даты, но не ранее 10 дней после подачи документов). Через 10 дней после подачи документов мэрия выдает certificat de non opposition, который нужен Вам для получении визы невесты.

достаточно моего свидетельства о разводе,

Достаточно для чего?

проставить в загранпаспорт что я не замужем?

Такие штампы не ставят.