Sachverhalt: A. Die Schweizer Bürger B._ und A._ haben am 18. August 1994 in Muttenz geheiratet. Am 10. Januar 2002 kam ihre gemeinsame Tochter C._ zur Welt. Im Januar 2004 wanderte die Familie nach Südafrika aus. Bei einem erneuten Aufenthalt in der Schweiz kam am 23. März 2004 der gemeinsame Sohn D._ auf die Welt, wobei die Familie kurz nach der Geburt wieder nach Südafrika zurückflog. Die ersten 18 Monate lebten die Eltern gemeinsam mit den Kindern in Somerset West (gediegener Vorort von Kapstadt). Danach nahm der Vater eine Stelle in Johannesburg an und pendelte während vier Jahren zwischen Somerset West und Johannesburg (Montag Abreise, Donnerstag Rückreise). Nachdem er diese Stelle im Juli 2009 verloren hatte, nahm er eine Stelle bei einer Schweizer Firma in Deutschland an. In dieser Zeit verbrachte er die Ferien und kumulierte Überstunden in Südafrika bei der Familie und telefonierte mehrmals wöchentlich mit ihr. Im April 2011 zog der Vater zurück nach Südafrika und liess sich aufgrund des Arbeitsmarktes und der ab dem Jahr 2010 aufgetretenen ehelichen Spannungen wieder in Johannesburg nieder, wo er seither mit seiner neuen Partnerin und deren Sohn lebt. Nach seinen Angaben besuchte er die Kinder seither alle zwei Wochen von Freitagabend bis Montagmorgen in Somerset West, telefonierte jeden zweiten Tag mit ihnen und verbrachte auch die Ferien mit ihnen; nach Darstellung der Mutter erfolgten die Besuche ungefähr einmal pro Monat. Beide Kinder gingen in Somerset West zur Schule; die Tochter besuchte zuletzt die dritte, ihr jüngerer Bruder die erste Klasse. Am 6. August 2011 erhielt der Vater von der Mutter eine SMS mit dem Inhalt, es sei wegen einer Geburtstagsparty nicht möglich, dass er die Kinder wie geplant zu sich auf Besuch nehmen könne. Am 10. August 2011 gingen die Kinder zum letzten Mal zur Schule. Am 12. August 2011 verbrachte sie die Mutter ohne Wissen des Vaters in die Schweiz. Die Kinder selbst wurden von der Mutter erst am Flughafen bzw. im Flugzeug über Ziel und Zweck der Reise informiert. B. Mit Gesuch vom 22. September 2011 beantragte der Vater die Rückführung der Kinder nach Südafrika und die Kontaktregelung für die Dauer des Verfahrens. Am 27. September 2011 verfügte der Appellationsgerichtspräsident Basel-Stadt ein Ausreiseverbot (mit Ausnahme von Südafrika) und die Hinterlegung sämtlicher Reisepapiere der Kinder sowie ein Verbot, neue Papiere zu beantragen. Dem Vater wurde das Recht eingeräumt, alle zwei Tage mit den Kindern zu telefonieren oder per Skype oder E-Mail zu kommunizieren. Sodann wurde ihnen eine Rechtsvertreterin bestellt. Am 13. Oktober 2011 reichte die Kindesvertreterin eine Zusammenfassung des Gesprächs mit den Kindern ein und am 19. Oktober 2011 wurden sie durch den Appellationsgerichtspräsidenten und Dr. phil. E._ angehört. Am 3. November 2011 fand das Vermittlungsverfahren statt, bei welchem beide Parteien anwesend waren. Es wurde ein Vergleich geschlossen, den die Mutter am 7. November 2011 widerrief. Vorgängig war auch eine Mediation ins Auge gefasst, angesichts der unvereinbaren Parteistandpunkte aber nicht durchgeführt worden. Mit an der Hauptverhandlung vom 7. November 2011, von welcher der nach Südafrika zurückgereiste Vater dispensiert worden war und an welchem die Mutter nochmals angehört wurde, gefälltem Urteil hiess der Appellationsgerichtspräsident den Rückführungsantrag des Vaters und der Kindesvertreterin gut, indem er die Mutter verpflichtete, die Kinder bis spätestens 28. Dezember 2011 auf ihre Kosten nach Südafrika zurückzuführen oder zurückführen zu lassen oder dem Vater zwecks Rückführung nach Südafrika zu übergeben, unter Anweisung der jeweils kantonal zuständige Vollzugsbehörde, im Weigerungsfall innert 60 Tagen seit Urteilszustellung die Kinder nach Südafrika zurückzuführen oder sie vom Gesuchsteller in der Schweiz abholen zu lassen. Sodann wurden die Vollzugsmodalitäten (Übergabe der Reisedokumente etc.) sowie das Kommunikationsrecht zwischen Vater und Kindern bis zum Rückführungszeitpunkt geregelt. C. Gegen dieses Urteil hat A._ am 5. Dezember 2011 eine Beschwerde in Zivilsachen erhoben mit den Begehren um dessen Aufhebung und Abweisung des Rückführungsgesuches, eventualiter um Rückweisung der Sache an die Vorinstanz zur Ermittlung des Sachverhaltes und zur Neubeurteilung, subeventualiter um Erlass folgender Auflagen im Zusammenhang mit der Rückführung: Verpflichtung des Vaters zur Anmeldung der Kinder an einer Schule in der Region Somerset West, zur Bezahlung der Schulkosten für zwei Jahre sowie zur Bezahlung des Mietzinsdepots und einer Wohnung in der Region Somerset West im Umfang von ca. Rand 8'500.-- pro Monat und Sicherstellung der entsprechenden Beträge. Mit Vernehmlassungen vom 15. Dezember 2011 verlangen sowohl der Vater als auch die Kindesvertreterin die Abweisung der Beschwerde und die Rückführung der Kinder. Der Vater beantragt zusätzlich mit einem Eventualbegehren, dass die Rückführung für den Fall, dass das bundesgerichtliche Urteil nicht mehr vor Weihnachten gefällt werden könne, auf einen späteren, jedoch dem kantonalen Urteil möglichst nahe liegenden Zeitpunkt anzuordnen sei. Die Kindesvertreterin verlangt ferner die unentgeltliche Verbeiständung und Entschädigung aus der Gerichtskasse. Mit Schreiben vom 19. Dezember 2011 berichtete die Kindesvertreterin über ihr Telefonat mit D._, nachdem die Mutter dieses doch noch ermöglicht hatte. Mit Verfügung vom 23. Dezember 2011 wurde der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt. Am 27. und 29. Dezember 2011 reichte die Mutter je eine Stellungnahme zu den Vernehmlassungen des Vaters und der Kindesvertreterin ein. Mit Schreiben vom 29. Dezember 2011 verwies der Vater auf eine Vereinbarung betreffend Verkauf der Liegenschaft in F._. Mit Schreiben vom 30. Dezember 2011 hat die Mutter hierzu Stellung genommen. 