Sachverhalt: A. A.a Z._, geb. 2001, ist die Tochter von Y._, Staatsbürgerin der Elfenbeinküste, und von X._, heimatberechtigt in A._. Sie ist Bürgerin der Elfenbeinküste und der Schweiz. Zur Zeit ihrer Geburt lebten die nicht verheirateten Eltern in der Elfenbeinküste. Der Vater, X._, hat seine Tochter gegenüber den ivorischen Behörden anerkannt und ist als Vater im Geburtenregister eingetragen. A.b Im Jahr 2002 reiste X._ im Einverständnis von Y._ mit der gemeinsamen Tochter in die Schweiz. Anfang Oktober 2002 reiste Y._ nach und lebte fortan mit der gemeinsamen Tochter und X._ zusammen. A.c Die Beziehung zwischen den Eltern gestaltete sich als schwierig. Am 16. Mai 2008 unterrichtete der am 3. Februar 2005 ernannte Beistand des Kindes die Vormundschaftsbehörde der Stadt B._ über die inzwischen erfolgte Heirat von Y._ mit einem französischen Staatsbürger und äusserte dabei die Vermutung, diese werde bald mit ihrer Tochter nach Frankreich ziehen. B. B.a Am 30. Juli 2008 erhob X._ beim Bezirksrat Zürich Klage gegen Y._ mit den Begehren um Feststellung, dass die elterliche Sorge über die gemeinsame Tochter ihm allein zustehe; ferner wurde beantragt, die Obhut über das Kind ihm zuzuteilen, Y._ ein angemessenes Besuchsrecht einzuräumen und eine Unterhaltsregelung zu treffen. Im Sinne einer superprovisorischen Massnahme wurde beantragt, Y._ vorsorglich bis zum rechtskräftigen Abschluss des Verfahrens unter Androhung der Strafen nach Art. 292 StGB zu verbieten, die gemeinsame Tochter Z._ ins Ausland zu verbringen. Der Bezirksrat trat mit Präsidialverfügung vom 31. Juli 2008 auf die Klage nicht ein und überwies sie zuständigkeitshalber der Vormundschaftsbehörde der Stadt B._. Am 6. August 2008 gelangte X._ an diese Behörde mit dem Begehren, Y._ superprovisorisch zu verbieten, die gemeinsame Tochter am folgenden Tag und bis auf Weiteres ins Ausland zu verbringen. Mit Beschluss vom 12. August 2008 wies die Vormundschaftsbehörde die Anträge von X._ ab, soweit sie darauf eintrat. Mit Beschluss vom 6. November 2008 wies der Bezirksrat Zürich die Beschwerde von X._ gegen den Beschluss der Vormundschaftsbehörde der Stadt B._ vom 12. August 2008 ab, soweit sie nicht gegenstandslos geworden war. B.b Mit Beschluss vom 15. Juni 2009 wies das Obergericht des Kantons Zürich, II. Zivilkammer, den von X._ gegen den Beschluss des Bezirksrats Zürich vom 6. November 2008 erhobenen Rekurs ab. C. Gegen den obergerichtlichen Beschluss hat X._ beim Bundesgericht am 10. Juli 2009 Beschwerde in Zivilsachen eingelegt. Er beantragt, den angefochtenen Beschluss des Obergerichts aufzuheben (1), ferner festzustellen, dass die gemeinsame Tochter unter seiner elterlichen Sorge, evtl. unter der gemeinsamen elterlichen Sorge der Parteien stehe (2); das Verfahren sei zur Regelung von Obhut, Besuchsrecht und Unterhaltszahlungen an die Vorinstanz zurückzuweisen (3). Für das bundesgerichtliche Verfahren sei ihm die unentgeltliche Rechtspflege zu gewähren (4). Y._ schliesst in ihrer Vernehmlassung vom 12. Oktober 2009 dahin, auf die Beschwerde sei nicht einzutreten, eventuell sei sie abzuweisen. Auch sie ersucht um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren. Das Obergericht hat auf Vernehmlassung verzichtet. D. Auf die gegen den obergerichtlichen Beschluss zusätzlich erhobene kantonale Nichtigkeitsbeschwerde trat das Kassationsgericht des Kantons Zürich mit Beschluss vom 22. Juli 2009 nicht ein.