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 <ref-law> 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.

Erwägungen:
1.1 Das Kassationsgericht des Kantons Zürich ist auf die gegen den obergerichtlichen Beschluss vom 15. Juni 2009 erhobene Nichtigkeitsbeschwerde nicht eingetreten mit der Begründung, beim angefochtenen Beschluss handle es sich um einen Rekursentscheid über den Beschluss des Bezirksrats betreffend elterliche Sorge, wobei der Bezirksrat über eine Beschwerde gegen den Beschluss der Vormundschaftsbehörde, also als Beschwerdeinstanz, entschieden habe. Gegen den obergerichtlichen Beschluss (Rekursentscheid) sei daher die Nichtigkeitsbeschwerde nicht gegeben (<ref-law>). Dieser Entscheid erwuchs in Rechtskraft. Ist die Nichtigkeitsbeschwerde gegen den obergerichtlichen Beschluss vom 15. Juni 2009 nicht zulässig, bildet der angefochtene obergerichtliche Beschluss einen letztinstanzlichen Entscheid im Sinn von <ref-law>. Angefochten sind Kindesschutzmassnahmen, mithin eine Zivilsache im Sinn von Art. 72 Abs. 2 lit. b Ziff. 7 BGG. Gerügt wird eine Verletzung von <ref-law>. Ferner wird geltend gemacht, das Obergericht habe <ref-law> falsch angewendet. Die Beschwerde in Zivilsachen ist damit zulässig.
1.2 Der Beschwerdeführer war im kantonalen Verfahren Partei und ist mit seinen Anträgen unterlegen. Er verfügt damit entgegen der Ansicht der Beschwerdegegnerin über ein rechtlich geschütztes Interesse an der Überprüfung des angefochtenen Beschlusses (Art. 76 Abs. 1 lit. a und b BGG); dies umso mehr als er nebst einer Verletzung von <ref-law> auch eine Missachtung seiner Parteirechte (Recht auf einen begründeten Entscheid [<ref-law>]) rügt.
2. 2.1 Der Beschwerdeführer macht geltend, das Obergericht stelle im angefochtenen Beschluss zwar fest, dass die Beschwerdegegnerin mit ihrer Tochter in Frankreich wohne, habe sich aber trotz entsprechender Ausführungen in der Rekursschrift mit keinem Wort zur Bedeutung des Wohnsitzwechsels der Tochter geäussert. Das Obergericht habe den Entscheid ungenügend begründet und damit <ref-law> verletzt.
2.2 Dem angefochtenen Entscheid lässt sich zwar nicht ausdrücklich, im Gesamtzusammenhang betrachtet aber unmissverständlich entnehmen, dass das Obergericht dem Wegzug des Kindes mit seiner Mutter keine Bedeutung beigemessen und diesem Umstand daher nicht berücksichtigt hat. Der Beschwerdeführer war denn auch in der Lage, das Urteil insoweit sachgerecht anzufechten (zu den Anforderungen an die Begründung des Entscheids: <ref-ruling> E. 4.3 S. 540; <ref-ruling> E. 2b S. 102 f.; <ref-ruling> E. 2a S. 149; <ref-ruling> E. 2c S. 34; <ref-ruling> E. 2c S. 14 f., je mit Hinweisen; <ref-ruling> E. 3.3 S. 445). Von einer Verletzung von <ref-law> kann keine Rede sein.
3. 3.1 Das Recht der Elfenbeinküste, wo das Kind geboren wurde, verleiht das alleinige Sorgerecht dem Vater. Der Beschwerdeführer verlangt, dass das alleinige (eventualiter das gemeinsame) Sorgerecht über die Tochter Z._ festgestellt und das eingeleitete Verfahren betreffend Kindesschutzmassnahmen weitergeführt wird. Er rügt als Erstes die Annahme des Obergerichtes, durch den Umzug in die Schweiz sei das Sorgerecht in Anwendung von <ref-law> auf die Mutter übergegangen. Er kritisiert eingehend die Lehrmeinung, dass die Anknüpfung an den Aufenthaltsort des Kindes ändern könne und die Beschwerdegegnerin nach erfolgtem Zuzug in die Schweiz das alleinige Sorgerecht habe.
3.2 Das Obergericht hat unter Hinweis auf die einschlägige Lehre überzeugend begründet, dass die Anknüpfung an den gewöhnlichen Aufenthalt gemäss <ref-law> wandelbar ist und daher zu verschiedenen Zeiten entsprechend dem jeweiligen Aufenthaltsort des Kindes unterschiedliches Recht zur Anwendung gelangt. Auf die entsprechende Erwägung des angefochtenen Entscheids kann verwiesen werden. Insoweit ist eine Verletzung von Bundesrecht nicht auszumachen.
4. 4.1 Als Zweites wendet der Beschwerdeführer ein, bei Annahme eines "beweglichen Anknüpfungsbegriffs" gelte es zu berücksichtigen, dass Mutter und Kind vor Abschluss des Verfahrens nach Frankreich gezogen seien: Nach französischem Recht stehe das Sorgerecht beiden Eltern gemeinsam zu, sodass das Obergericht von einem solchen gemeinsamen Sorgerecht hätte ausgehen müssen. Damit habe es <ref-law> willkürlich angewendet, wonach dem Urteil derjenige Sachverhalt zugrunde zu legen ist, der im Zeitpunkt der Urteilsfällung besteht.
4.2 Das Obergericht geht im angefochtenen Entscheid davon aus, das Übereinkommen über die Zuständigkeit der Behörden und das anzuwendende Recht auf dem Gebiet des Schutzes von Minderjährigen (MSA) sei im vorliegenden Fall auf die elterliche Sorge nicht anwendbar, da diese als Recht kraft Gesetzes keine Schutzmassnahme im Sinn des Abkommens darstelle.
4.2.1 Das Obergericht schliesst sich insoweit bedeutender Lehre an (Kurt Siehr, Zürcher Kommentar zum IPRG, 2. Aufl. 2004, N. 7 zu <ref-law>). Es übersieht dabei allerdings, dass der Beschwerdeführer nebst der Feststellung der elterlichen Sorge auch um die Regelung der Obhutszuweisung, des Besuchsrechts und des Unterhaltsbeitrages ersucht hat, womit das Feststellungsbegehren im Ergebnis lediglich Vorfrage bezüglich der anbegehrten Massnahmen bildet. Dass die verlangten materiellen Anordnungen - mit Ausnahme der Unterhaltsregelung - zu den Schutzmassnahmen des MSA zu zählen sind, ist in Rechtsprechung und Lehre bereits dargelegt worden (siehe dazu: <ref-ruling> E. 4 S. 179; Urteil 5A_220/2009 vom 30. Juni 2009 E. 4.1.1, unter Hinweis auf <ref-ruling>; Siehr, a.a.O., N. 7 in fine zu <ref-law>; Derselbe, a.a.O., N. 27 zu <ref-law> zur Ausnahme bezüglich des Unterhalts). Somit kann nicht gesagt werden, das MSA sei nicht anwendbar.
4.2.2 Gemäss Art. 1 MSA sind die Gerichte und Verwaltungsbehörden desjenigen Staates, in dem ein Minderjähriger seinen gewöhnlichen Aufenthalt hat, unter Vorbehalt der Bestimmungen der Art. 3, 4 und 5 Abs. 3 zuständig, Massnahmen zum Schutze der Person oder des Vermögens des Minderjährigen zu treffen. Im vorliegenden Fall ist unbestritten, dass die Beschwerdegegnerin und das gemeinsame Kind der Parteien zu Beginn des Verfahrens ihren gewöhnlichen Aufenthalt in der Schweiz hatten. Der Beschwerdeführer hat aber ordnungsgemäss geltend gemacht, Mutter und Kind seien kurz nach Anhebung des Verfahrens nach Frankreich gezogen; überdies soll die Beschwerdegegnerin einen Franzosen geheiratet haben. Das Obergericht hat diesen Umständen keine Beachtung geschenkt und hat damit auch nicht erörtert, ob die Beschwerdegegnerin und das Kind in Frankreich einen neuen gewöhnlichen Aufenthalt begründet haben. Damit aber ist eine zentrale Frage unbeantwortet geblieben, zumal das MSA den Grundsatz der perpetuatio fori nicht kennt (<ref-ruling> E. 2a). Somit kann zurzeit auch nicht abschliessend über die Zuständigkeit der schweizerischen Gerichte befunden werden.
4.3 Im vorliegenden Fall gilt es zu berücksichtigen, dass am 1. Juli 2009 das Übereinkommen über die Zuständigkeit, das anzuwendende Recht, die Anerkennung, Vollstreckung und Zusammenarbeit auf dem Gebiet der elterlichen Verantwortung und der Massnahmen zum Schutz von Kindern (SR 0.211.231.01; HKsÜ) und die dem Übereinkommen angepasste Fassung von <ref-law> (SR 291) in Kraft getreten sind (AS 2009 3085 bzw. AS 2009 3078). Nach diesem Übereinkommen begründet der gewöhnliche Aufenthalt des Kindes die Zuständigkeit und sind bei einem Wechsel des gewöhnlichen Aufenthalts in einen anderen Vertragsstaat grundsätzlich die Behörden dieses Staates zuständig (Art. 5). Es steht dem Bundesgericht nicht zu, als erste Instanz die Frage zu entscheiden, ob dieses Übereinkommen bzw. die neue Fassung von <ref-law> auf den konkreten Fall zur Anwendung gelangt. Infolgedessen kann zurzeit auch den Anträgen des Beschwerdeführers auf Feststellung seines Sorgerechts und auf Erlass von Kindesschutzmassnahmen nicht stattgegeben werden (vgl. Urteil 5A_220/2009 vom 30. Juni 2009 E. 4.1.1). Der angefochtene Entscheid ist aufzuheben und die Sache zu neuem Entscheid im Sinn der bisherigen Ausführungen an die Vorinstanz zurückzuweisen.
5. Bei diesem Ausgang des Verfahrens wird die Beschwerdegegnerin kostenpflichtig (<ref-law>) und hat den Beschwerdeführer für das bundesgerichtliche Verfahren zu entschädigen (<ref-law>).
6. 6.1 Der Beschwerdeführer ersucht um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren. Er ist bedürftig und sein Standpunkt galt nicht als von vornherein aussichtslos. Dem Gesuch um unentgeltliche Rechtspflege ist somit zu entsprechen und dem Beschwerdeführer ein Rechtsbeistand zu bestellen (Art. 64 Abs. 1 und 2 BGG).
6.2 Das Gesuch der Beschwerdegegnerin ist ebenso gutzuheissen, da die Voraussetzungen für die Gewährung der unentgeltlichen Rechtspflege auch in ihrem Fall erfüllt sind und sie zur Wahrung ihrer Interessen auf einen Rechtsbeistand angewiesen ist (Art. 64 Abs. 1 und 2 BGG). Aufgrund der Gewährung der unentgeltlichen Rechtspflege an die unterliegende Beschwerdegegnerin sind die Gerichtskosten einstweilen auf die Bundesgerichtskasse zu nehmen. Da die Beschwerdegegnerin offensichtlich nicht in der Lage ist, den Beschwerdeführer für das bundesgerichtliche Verfahren zu entschädigen, ist beiden Rechtsbeiständen für ihre Bemühungen im bundesgerichtlichen Verfahren ein Honorar aus der Bundesgerichtskasse zu entrichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der Beschluss des Obergerichts des Kantons Zürich, II. Zivilkammer, vom 15. Juni 2009 wird aufgehoben und die Sache zu neuer Entscheidung im Sinn der Erwägungen an das Obergericht zurückgewiesen.
2. Die Gesuche der Parteien um unentgeltliche Rechtspflege werden gutgeheissen. Dem Beschwerdeführer wird Rechtsanwältin Lisa Zaugg als unentgeltliche Anwältin, der Beschwerdegegnerin Rechtsanwalt Thierry Frei als unentgeltlicher Anwalt bestellt.
3. Die Gerichtskosten von Fr. 2'000.-- werden der Beschwerdegegnerin auferlegt, einstweilen aber auf die Bundesgerichtskasse genommen.
4. Den unentgeltlichen Anwälten wird für das bundesgerichtliche Verfahren je eine Entschädigung von Fr. 2'000.-- aus der Bundesgerichtskasse entrichtet.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 26. Oktober 2009
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Zbinden