Sachverhalt: A. Y._ (geb. 1963) und X._ (geb. 1969) sind die nicht verheirateten Eltern des 2007 in Pennsylvania, USA, geborenen Sohns A._. Die elterliche Beziehung gestaltete sich schwierig. Nach Streitigkeiten verliess die Mutter mit A._ den gemeinsamen Haushalt und erwirkte am 10. Dezember 2007 einen temporary protection from abuse order, mit welchem dem Vater jeder Kontakt zu seinem Sohn untersagt wurde. Am 20. Dezember 2007 erteilte der Court of Common Pleas of Centre County, Pennsylvania, der Mutter die primary physical custody über A._ und dem Vater die partial physical custody für genau festgelegte Besuchszeiten; ferner ordnete das Gericht an, dass das Kind nicht ohne Zustimmung beider Parteien aus dem Centre County entfernt werden dürfe. Am 9. Januar 2008 wurde den Parteien ein geteiltes Sorgerecht zugesprochen und festgehalten, dass weiterhin die am 20. Dezember 2007 getroffene Obhutsregelung gelten soll. Im gleichen Entscheid vom 9. Januar 2008 erlaubte das Gericht der Mutter, gemeinsam mit ihrem Sohn vom 11. Januar 2008 bis längstens 26. Januar 2008 in die Schweiz zu reisen. Die Mutter kehrte indessen nicht zeitgerecht in die USA zurück; ein Gesuch um Verlängerung des Aufenthaltes in der Schweiz wies das Gericht mit Entscheid vom 13. Februar 2008 ab. Trotzdem blieb die Mutter mit ihrem Sohn in der Schweiz. B. Gestützt auf ein Gesuch des Vaters um Rückführung von A._ vom 13. Mai 2008 befahl das Bezirksgericht Meilen der Mutter mit Verfügung vom 20. Oktober 2008, das Kind innert 30 Tagen nach Rechtskraft der Verfügung auf ihre Kosten in die USA zurückzubringen oder zurückbringen zu lassen. Im Zuge des dagegen eingereichten Rekurses der Mutter ordnete das Obergericht des Kantons Zürich weitere Abklärungen an. Mit Beschluss vom 26. Januar 2009 wies es das Rückführungsbegehren schliesslich ab. In dahingehender Gutheissung der Beschwerde des Vaters ordnete das Bundesgericht in seinem Urteil vom 16. April 2009 (5A_105/2009) im Grundsatz die Rückführung des Kindes innert 30 Tagen an, wobei es diese zur Vermeidung einer drohenden Trennung von Mutter und Kind von Einreise- und Aufenthaltsgarantien für die Mutter abhängig machte. Im Einzelnen lautete die Anordnung wie folgt: 2. Die Beschwerdegegnerin wird unter Androhung der Bestrafung nach Art. 292 StGB verpflichtet, A._, geb. 2007, innert 30 Tagen auf ihre Kosten in die USA zurückzubringen oder zurückbringen zu lassen. 3. Die Rückführungsfrist gemäss Ziff. 2 beginnt zu laufen, sobald die Beschwerdegegnerin seitens der zuständigen Behörden der USA die schriftliche und verbindliche Garantie erhalten hat, dass sie mit ihrem jetzigen Visum des Typs B1/B2 frei in die USA einreisen und sich dort bis mindestens zum rechtskräftigen Abschluss des Sorgerechtsverfahrens über A._ aufhalten darf, oder sobald ihr die zuständigen Behörden ein Visum eines Typs ausgestellt haben, welcher automatisch einen entsprechenden unbedingten Rechtsanspruch gibt. Die Frist gemäss Ziff. 2 beginnt auch zu laufen, wenn die Beschwerdeführerin nicht innert 30 Tagen ab Zustellung dieses Urteils bei den zuständigen Behörden mit einem vollständigen und allen notwendigen Unterlagen versehenen Gesuch entsprechende Garantien oder ein entsprechendes Visum beantragt hat. 4. Die Rückführungsverpflichtung gemäss Ziff. 2 fällt dahin, wenn die zuständigen Behörden das Gesuch der Beschwerdeführerin im Sinn von Ziff. 3 offiziell abschlägig beantwortet haben. C. Mit Eingabe vom 15. Juli 2009 fragte die Mutter das Obergericht des Kantons Zürich an, ob sie davon ausgehen dürfe, dass die Rückführungsverpflichtung dahingefallen sei. Trotz ihrer Bemühungen habe sie keine Garantie für die freie Einreise und den Aufenthalt in den USA erhalten. Mit Eingabe vom 17. Juli 2009 an das Obergericht stellte der Vater die Begehren, es sei der unbenützte Ablauf der Rückführungsfrist festzustellen und es sei dem Amt für Jugend und Berufsberatung (nachfolgend Jugendamt) eine Frist von 30 Tagen anzusetzen, um auf eine freiwillige Rückführung hinzuwirken, verbunden mit der Anordnung des polizeilichen Vollzuges bei Scheitern einer freiwilligen Rückführung. Das Obergericht überwies diese beiden Eingaben dem Jugendamt als kantonale Vollzugsbehörde. Dieses schickte das Dossier am 4. August 2009 zurück an das Obergericht mit der Begründung, es liege nicht in der Kompetenz der Vollstreckungsbehörde, über die umstrittene Frage des Eintritts von Bedingungen zu entscheiden. Mit Beschluss vom 7. August 2009 trat das Obergericht auf den Antrag des Vaters nicht ein, wies den Antrag der Mutter ab und schickte die Akten an das Jugendamt zurück. Mit Eingabe vom 24. August 2009 stellte die Mutter die Begehren, es sei die Rückführungsverpflichtung als dahingefallen zu erklären und die Rückführung zu verweigern und es sei dem Kind ein Kindesvertreter beizugeben. Am 25. September 2009 verfügte das Jugendamt, dass die Rückführung von A._ aufgrund des Dahinfallens der Rückführungsverpflichtung gemäss Ziff. 2 und 3 des bundesgerichtlichen Entscheides nicht vollstreckt werde. Ferner wies es die Anträge des Vaters ab, trat auf das Gesuch um Bestellung eines Kindesvertreters nicht ein und regelte die Kosten. D. Gegen diese Verfügung hat der Vater am 8. Oktober 2009 bei der Bildungsdirektion des Kantons Zürich einen Rekurs erhoben mit den Begehren, die Rückführung sei zu vollstrecken, indem der Mutter eine Frist von 30 Tagen zur freiwilligen Rückführung des Sohnes angesetzt und andernfalls der polizeiliche Vollzug angeordnet werde, eventualiter sei die Rückführung zu vollstrecken, indem der Mutter eine Frist von 30 Tagen eingeräumt werde, um in die USA einzureisen und im Fall der erfolgreichen Einreise den Sohn innerhalb eines Tages nachzuziehen. Ausserdem verlangt der Vater die unentgeltliche Rechtspflege. Die Direktion überwies diese Eingabe am 23. Oktober 2009 an das Bundesgericht. Mit Vernehmlassung vom 6. November 2009 verlangte die Mutter, die von der Bildungsdirektion an das Bundesgericht überwiesene Beschwerde sei abzuweisen und es sei ihr die unentgeltliche Rechtspflege zu gewähren. Das Jugendamt hat auf eine Vernehmlassung verzichtet. 