Sachverhalt:
A. Die Parteien lebten bis April 2006 gemeinsam in Südafrika. Sie sind nicht verheiratet und haben den gemeinsamen Sohn A._, geb. 2006.
Im Juni 2006 klagte die Mutter beim High Court of South Africa (Cape of Good Hope Provincial Division) auf Regelung des väterlichen Besuchsrechts während ihres Aufenthaltes in Kapstadt. Mit Widerklage verlangte der Vater die Zuteilung der gemeinsamen elterlichen Sorge sowie ein fünfjähriges Ausreiseverbot für Mutter und Kind. Dagegen erhob die Mutter am 15. September 2006 Einspruch.
Am 14. Oktober 2006 reiste die Mutter mit A._ in die Schweiz aus. Darauf beantragte der Vater beim südafrikanischen High Court die Feststellung, dass das Gericht im Zeitpunkt der Ausreise das Sorgerecht im Sinn von Art. 3 des Haager Übereinkommens über die zivilrechtlichen Aspekte internationaler Kindesentführung (HEntfÜ, SR 0.211.230.02) innegehabt habe. Mit Urteil vom 22. Dezember 2006 stellte B.M. Griesel, Richter am High Court, fest, dass dieser als eine Institution zu betrachten sei, der Sorgerechte im Sinn von Art. 3 HEntfÜ beigemessen werden könnten, und dass das Gericht vor dem Umzug von A._ in die Schweiz Sorgerechte im Sinn von Art. 3 i.V.m. Art. 5 lit. a HEntfÜ erworben habe. Gegen dieses Urteil erklärte die Mutter in Südafrika Appellation, über die bisher nicht entschieden worden ist.
B. Mit Schreiben vom 21. Mai 2007 an das Bezirksgericht Arlesheim verlangte der Vater die Feststellung der widerrechtlichen Verbringung von A._ in die Schweiz und dessen unverzügliche Rückführung nach Südafrika.
Sowohl das Bezirksgericht Arlesheim als auch das Kantonsgericht Basel-Landschaft wiesen das Rückführungsgesuch mit Urteil vom 3. August bzw. 30. Oktober 2007 ab. Sie erwogen, dass die Mutter im Zeitpunkt der Ausreise nach südafrikanischem Recht das alleinige Sorgerecht innegehabt habe und sich diese Rechtslage erst mit dem Entscheid vom 22. Dezember 2006 verändert habe. Dieser Entscheid könne jedoch nicht im Sinn einer rückwirkenden Rechtsfortbildung die Widerrechtlichkeit des Verbringens von A._ begründen.
C. Gegen das Urteil des Kantonsgerichts hat der Vater am 30. November 2007 Beschwerde in Zivilsachen erhoben, im Wesentlichen mit den Begehren um dessen Aufhebung, um Feststellung des widerrechtlichen Verbringens und um unverzügliche Rückführung von A._, eventualiter um Rückweisung der Sache an die Vorinstanz. Ferner wird um unentgeltliche Rechtspflege und um Anordnung ersucht, dass die Ausweispapiere von A._ weiterhin beim Bezirksgericht Arlesheim hinterlegt bleiben. Mit Vernehmlassung vom 17. Dezember 2007 schliesst die Mutter auf Abweisung der Beschwerde und verlangt für den gegenteiligen Eventualfall, A._ einen fachlich geeigneten Vertreter zu bestellen.

Erwägungen:
1. Bei Rückführungsentscheiden nach dem HEntfÜ geht es um die Regelung der Rechtshilfe zwischen den Vertragsstaaten (<ref-ruling> E. 2b S. 224), die in unmittelbarem Zusammenhang mit der Respektierung und Durchsetzung ausländischen Zivilrechts steht (Art. 72 Abs. 2 lit. b Ziff. 1 BGG). Angefochten ist ein letztinstanzlicher Entscheid (<ref-law>) und die Beschwerdefrist von zehn Tagen ist eingehalten (<ref-law>). Die Beschwerde in Zivilsachen ist somit gegeben.
In sachlicher Hinsicht kann mit ihr insbesondere die Verletzung von Völkerrecht geltend gemacht werden, dessen Anwendung vom Bundesgericht frei geprüft wird (Art. 95 lit. b i.V.m. <ref-law>). Demgegenüber können Sachverhaltsfeststellungen nur gerügt werden, wenn sie offensichtlich unrichtig und für den Ausgang des Verfahrens entscheidend sind (<ref-law>), wobei "offensichtlich unrichtig" mit "willkürlich" gleichzusetzen ist (<ref-ruling> E. 1.2.2 S. 252).
2. Zwischen den Parteien ist umstritten, ob das Verbringen von A._ in die Schweiz widerrechtlich im Sinn von Art. 3 lit. a HEntfÜ war.
Der Vater leitet die Widerrechtlichkeit aus dem erwähnten südafrikanischen Entscheid vom 22. Dezember 2006 ab. Darin hielt Richter Griesel zunächst fest, dass das väterliche Begehren um Zuspruch eines Sorgerechts mit Blick auf das Haager Rückführungsübereinkommen neuartig (res nova) und im südafrikanischen Recht kein Präzedenzfall bekannt sei (Rz. 18 und 25). Sodann hielt er fest, dass der Vater selbst über keinerlei Sorgerechte verfüge, weil das Sorgerecht über ein aussereheliches Kind nach dem Common law ausschliesslich bei der Mutter liege; zwar könne der Vater gemäss dem "Natural Fathers Act 86" bei gegebenen Voraussetzungen gestützt auf eine gerichtliche Feststellung Sorgerechte über das Kind erwerben, aber bis zu diesem Zeitpunkt verfüge er über keinerlei Sorgerechte (Rz. 34), und Richter Griesel lehnte es auch ausdrücklich ab, dem Vater unter einem anderen Titel - namentlich unter dem seinerzeit noch nicht in Kraft stehenden "Children's Act 38" - irgendwelche Sorgerechte anzuerkennen (insb. Rz. 39). Im Anschluss daran hielt Richter Griesel fest, dass sich das Sorgerecht aber beim Gericht befinden könne, sobald dieses mit dem Gegenstand des Sorgerechts befasst sei (Rz. 42 ff.). Für den Übergang von Sorgerechten auf das mit diesem Thema befasste Gericht gebe es zwar keinerlei Präzedenzfälle in Südafrika, wohl aber - nicht unumstrittene (Rz. 43) - Präjudizien aus der englischen Rechtsprechung (Rz. 44 f.), und es sei kein Grund ersichtlich, diese nicht auch für das südafrikanische Recht zu übernehmen (Rz. 46). Als Zeitpunkt für den Übergang sei - wiederum anlehnend an englische Entscheide - auf die Zustellung des Antrags auf Zuteilung von Sorgerechten an die andere Partei abzustellen (Rz. 47 ff.), d.h. vorliegend auf den am 15. September 2006 erhobenen Einspruch der Mutter gegen das väterliche Widerklagebegehren um Zuspruch von Sorgerechten (Rz. 50).
Das Kantonsgericht hat erwogen, dass das südafrikanische Recht erst mit dem erwähnten Entscheid um das Institut des gerichtlichen Sorgerechts erweitert worden sei und dieses im Zeitpunkt der Ausreise folglich noch nicht bestanden habe. Im Übrigen ziele das Abkommen, wie Art. 3 lit. b HEntfÜ zeige, auf den Schutz tatsächlich ausgeübter Sorgerechtsverhältnisse, während virtuelle Sorgerechte, wie sie vom High Court beansprucht würden, nicht darunter fielen. Wenn schon hätte dieser konkrete materielle Anordnungen treffen müssen; Richter Griesel gehe aber selbst davon aus, dass das Gericht vor der Ausreise kein Sorgerecht ausgeübt habe.
Der Vater erblickt in diesen Erwägungen eine Verletzung des Haager Rückführungsübereinkommens. Er bringt vor, in Ziff. 1.3 des Dispositivs des südafrikanischen Entscheides vom 22. Dezember 2006 sei ausdrücklich eine Verletzung von Art. 3 lit. a HEntfÜ festgestellt worden, und gemäss Art. 14 HEntfÜ sei das Kantonsgericht an diesen Entscheid gebunden. In Verletzung des Übereinkommens habe es den Entscheid des High Courts einer eigenen Interpretation unterzogen, obwohl Richter Griesel explizit festgehalten habe, dass der High Court bereits vor dem Verbringen das Sorgerecht über A._ erworben habe. Im Übrigen sei mit diesem Entscheid kein neues Recht geschaffen, sondern lediglich die bestehende Rechtslage in Südafrika festgehalten worden; dass dabei Entscheide anderer Länder hinzugezogen worden seien, sei für den angelsächsischen Rechtsbereich üblich. Sodann habe er bereits vor Kantonsgericht den Entscheid Girdwood vs Girdwood eingereicht, aus welchem sich ergebe, dass im südafrikanischen Recht seit Jahrhunderten die Institution des Gerichts als "upper Guardian" bestehe; dies sei im Rahmen von <ref-law> zu berücksichtigen. Wie sich aus weiteren, bereits vor Kantonsgericht eingereichten, aber nicht berücksichtigten Entscheiden aus England, Irland, Neuseeland und Kanada ergebe, würden auch andere angelsächsische Länder das Institut des gerichtlichen Sorgerechts kennen.
3. Zu prüfen ist die zwischen den Parteien strittige Frage, ob die Ausreise in die Schweiz widerrechtlich war.
Das Verbringen eines Kindes über die Landesgrenze ist dann widerrechtlich, wenn dadurch das Sorgerecht verletzt wird, das einer Person, Behörde oder sonstigen Stelle allein oder gemeinsam nach dem Recht des Staates zusteht, in welchem das Kind unmittelbar vor dem Verbringen oder Zurückhalten seinen gewöhnlichen Aufenthalt hatte (Art. 3 lit. a HEntfÜ), und dieses Recht im Zeitpunkt des Verbringens oder Zurückhaltens allein oder gemeinsam tatsächlich ausgeübt wurde oder ausgeübt worden wäre, wenn das Verbringen oder Zurückhalten nicht stattgefunden hätte (Art. 3 lit. b HEntfÜ). Das genannte Sorgerecht kann insbesondere kraft Gesetzes, aufgrund einer gerichtlichen oder behördlichen Entscheidung oder aufgrund einer nach dem Recht des betreffenden Staates wirksamen Vereinbarung bestehen (Art. 3 Abs. 2 HEntfÜ).
Das Vorbringen des Beschwerdeführers, eine Sorgerechtsentscheidung dürfe nicht materiell überprüft werden, trifft an sich zu: Gemäss Art. 16 HEntfÜ darf der ersuchte Staat keinen Sachentscheid über das Sorgerecht treffen. Vorliegend geht es aber nicht darum: Im südafrikanischen Entscheid vom 22. Dezember 2006 ist nicht materiell über das Sorgerecht entschieden worden und ebenso wenig wird im vorliegenden Verfahren über diese Frage befunden (Art. 19 HEntfÜ); vielmehr ist im Rückführungsverfahren zu prüfen, ob das Verbringen des Kindes widerrechtlich im Sinn von Art. 3 HEntfÜ war. Dieser Entscheid steht nicht dem Herkunftsstaat zu; vielmehr ist dieser Punkt, der eine von mehreren Voraussetzungen für die Anordnung der Rückführung ist, von den Gerichten des ersuchten Staates zu prüfen, wobei diese hierfür das Recht des Herkunftsstaates und dessen gerichtliche Entscheide unmittelbar berücksichtigen können (Art. 14 HEntfÜ).
Wie bereits erwähnt, ist das Verbringen oder Zurückhalten eines Kindes nach dem Wortlaut von Art. 3 lit. a HEntfÜ nur dann widerrechtlich, wenn das Sorgerecht verletzt wurde, das einer Person oder Behörde unmittelbar vor dem Verbringen des Kindes zustand. Massgeblich ist also die Sorgerechtslage, wie sie beim Verbringen bestanden hat; dieser Status quo ante soll wiederhergestellt werden, weshalb ein Verbringen kurz vor einer erwarteten Entscheidung keinen Rückführungsanspruch zu begründen vermag (Staudinger/Pirrung, Kommentar zum Bürgerlichen Gesetzbuch, 12. Aufl., Berlin 1994, Vorbem. zu Art. 19 EG BGB, N. 643; Bach/Gildenast, Internationale Kindesentführung, Bielefeld 1999, N. 53 und 54) und insbesondere auch ein nachträgliches Missbilligen durch einen Gerichtsentscheid nicht von Art. 3 HEntfÜ erfasst wird (Zürcher, Kindesentführung und Kindesrechte, Diss. Zürich 2005, S. 81; Siehr, Münchener Kommentar zum Bürgerlichen Gesetzbuch, Art. 21 EG BGB Anh. II, N. 27; ders., Entführung eines "Mündels des Gerichts" (ward of court) nach Deutschland, in: IPRax 2005, S. 528). Darauf wird zurückzukommen sein.
Das im anglo-amerikanischen Rechtsbereich entwickelte Institut des "Ward of Court", wonach das mit dem Sorgerecht befasste Gericht selbst zu dessen Inhaber wird, ist dem kontinentaleuropäischen Rechtsdenken fremd; ein "Ruhen" des Sorgerechts bei einer Behörde würde jedenfalls voraussetzen, dass dieses den Eltern entzogen worden ist. Dennoch sind solche Rechtserscheinungen unter Vorbehalt von Art. 20 HEntfÜ grundsätzlich hinzunehmen (Staudinger/Pirrung, a.a.O., N. 642, wo das Institut des "Ward of Court" ausdrücklich erwähnt wird; ebenso bei Bach/Gildenast, a.a.O., N. 51; Siehr, a.a.O., N. 28; vgl. sodann Siehr, IPRax 2005, S. 526), weil sich der Umfang des Sorgerechts nach dem nationalen Recht des Herkunftsstaates bemisst (Siehr, a.a.O., N. 28 f.; Bach/Gildenast, a.a.O., N. 60).
Vorliegend besteht jedoch die Besonderheit, dass die Rechtsfigur des "Ward of Court" oder eines analogen Institutes dem südafrikanischen Recht bislang unbekannt war und es zum ersten Mal mit dem (im Übrigen noch nicht rechtskräftigen) Entscheid von Richter Griesel in Erscheinung getreten ist. Der Vater behauptet zwar in seiner Beschwerde erneut eine seit Jahrhunderten bestehende Rechtserscheinung, wonach in Südafrika das Gericht bei Sorgerechtsverfahren als "upper Guardian" über Minderjährige auftrete. Aus dem von ihm ins Recht gelegten Entscheid im Scheidungsverfahren Girdwood vs Girdwood aus dem Jahr 1994 ergibt sich aber einzig, dass der High Court in seiner Funktion als "upper guardian of all dependent and minor children" das Recht hat, "to establish what was in the best interests of the children, and to make corresponding orders to ensure that such interests were effectively served and safeguarded"; das bedeutet nicht mehr und nicht weniger, als dass sich der High Court für zuständig erklärt hat, im Rahmen eines Scheidungsverfahrens die erforderlichen Kindesschutzmassnahmen zu treffen. Demgegenüber lässt sich dem vorgelegten Entscheid Girdwood vs Girdwood ein gerichtliches Sorgerecht, wie es vorliegend zur Debatte steht, nicht im Ansatz entnehmen. Ohnehin hätte sich Richter Griesel - sollten die durch nichts belegten Behauptungen des Vaters zutreffen - im vorliegenden Fall ganz konkret auf die Funktion des "upper Guardian" berufen und gestützt darauf auch tatsächlich ein Sorgerecht in Anspruch nehmen bzw. ausüben müssen, damit die Voraussetzung von Art. 3 lit. b HEntfÜ erfüllt wäre und von einer widerrechtlichen Verletzung im Sinn von Art. 3 HEntfÜ überhaupt die Rede sein könnte.
Indes trifft für beide Voraussetzungen (bestehendes Sorgerecht und tatsächliche Ausübung) genau das Gegenteil zu: Mit Bezug auf das gerichtliche Sorgerecht hat Richter Griesel ausdrücklich festgehalten, dass es in Südafrika keine Präzendenzfälle gebe (res nova), dass aber nichts dagegen spreche, Präjudizien englischer Gerichte auch für den Staat Südafrika zu übernehmen. Handelt es sich aber somit für das nationale Recht Südafrikas um eine Rechtsfortbildung oder Rechtsschöpfung, kann das Sorgerecht vor dieser Bildung bzw. Schöpfung neuen Rechts noch nicht im Sinn von Art. 3 lit. a HEntfÜ (im Zeitpunkt des Verbringens) beim Gericht geruht haben, umso weniger als infolge des hängigen Appellationsverfahrens offen ist, ob das Institut des "Ward of Court" oder eine analoge Rechtsfigur in Südafrika überhaupt eingeführt wird. Noch weniger könnte ein solches Sorgerecht im Sinn von Art. 3 lit. b HEntfÜ tatsächlich ausgeübt worden sein, lassen sich doch tatsächliche Verhältnisse begriffslogisch nicht rückwirkend schaffen. Damit gebricht es aber in jedem Fall an der zweiten Voraussetzung der Widerrechtlichkeit.
Die Tatsache, dass das Haager Übereinkommen für die Widerrechtlichkeit strikt auf den Zeitpunkt des Verbringens abstellt (vgl. auch die vorstehend zitierte einhellige Lehre, wonach spätere Entscheide unbeachtlich sein müssen), steht im Zusammenhang mit den Grundsätzen der Rechtsstaatlichkeit, der Rechtssicherheit und des Vertrauensschutzes: Die rechtsunterworfenen Parteien müssen objektiv wissen bzw. in Erfahrung bringen können, welches Recht zu einem bestimmten Zeitpunkt gilt und ob sie mit ihren Handlungen allenfalls dagegen verstossen. Am 15. Oktober 2006 durfte die Mutter als alleinige Sorgerechtsinhaberin im Vertrauen auf die damalige Rechtslage gutgläubig aus Südafrika ausreisen und musste nicht damit rechnen, dass sie - aufgrund einer rückwirkenden Rechtsschöpfung, die im Übrigen appelliert und damit in Schwebe ist - ein behördliches Sorgerecht verletzen würde. Im Übrigen hätte es dem Vater frei gestanden, vom High Court den Erlass vorsorglicher Massnahmen zu verlangen, etwa die Zuteilung der gemeinsamen Sorge während der Dauer des Hauptprozesses oder doch wenigstens eine Ausreisesperre (non-removal clause), die Hinterlegung des Passes von A._ oder eine ähnliche Vorkehrung.
Zusammenfassend ergibt sich, dass der High Court im Zeitpunkt des Verbringens kein (alleiniges oder geteiltes) Sorgerecht im Sinn von Art. 3 lit. a HEntfÜ haben konnte und dass er es in diesem Zeitpunkt jedenfalls nicht tatsächlich im Sinn von Art. 3 lit. b HEntfÜ ausübte. Ist aber das Verbringen von A._ demzufolge nicht widerrechtlich im Sinn von Art. 3 HEntfÜ, so mangelt es an einer notwendigen Voraussetzung zur Begründung des Rückführungsanspruches nach Art. 12 Abs. 1 HEntfÜ. Das angefochtene Urteil des Kantonsgerichts Basel-Landschaft, mit welchem das Begehren um Rückführung von A._ abgewiesen wurde, ist nach dem Gesagten konform mit dem Haager Rückführungsübereinkommen, und die dagegen gerichtete Beschwerde des Vaters ist abzuweisen.
4. Mit Bezug auf die Auferlegung der kantonalen Kosten rügt der Beschwerdeführer eine Verletzung von <ref-law>. Seine diesbezüglichen Ausführungen richten sich ausschliesslich gegen die obergerichtlichen Sachverhaltsfeststellungen, die nur auf Willkür hin überprüft werden können (dazu oben, E. 1). Er kritisiert, dass das Obergericht von einem Einkommen von ZAR 414'604.-- pro Jahr (Fr. 5'758.40 pro Monat) ausgegangen ist; davon seien noch Steuern von ZAR 100'665.60 und Sozialleistungen von ZAR 62'190.-- abzuziehen, weshalb es ZAR 251'748.40 pro Jahr (Fr. 3'496.50 pro Monat) betrage und somit unterhalb seines Existenzminimums von Fr. 4'120.-- liege.
Als Beweismittel legt er einzig eine - von offensichtlich mehreren - Seiten einer in Afrikaans abgefassten Steuerveranlagung vor, die ein Einkommen (Inkomste) von ZAR 414'604.-- und Abzüge (Aftrekkings) von ZAR 62'190.-- sowie einen Nettosteuerbetrag von ZAR 94'221.67 ausweist. Aus diesem Blatt ist aber weder ersichtlich, dass es sich beim Betrag von ZAR 62'190.-- um Sozialversicherungsabzüge handelt (die Beschwerdegegnerin macht geltend, es handle sich um allgemeine Steuerabzüge), noch ist damit belegt, dass der fällige Steuerbetrag effektiv bezahlt worden ist, wie dies erforderlich wäre, damit er in der Bedarfsberechnung berücksichtigt werden könnte. Bereits vor diesem Hintergrund hat das Kantonsgericht keine willkürliche Sachverhaltsfeststellung getroffen, wenn es von einem anrechenbaren Einkommen von ZAR 414'604.-- pro Jahr bzw. von Fr. 5'758.40 pro Monat ausgegangen ist.
Bei diesem Resultat würden sich weitere Ausführungen zur Bedarfsberechnung erübrigen. Der Vollständigkeit halber sei aber zu den Ausgabenpositionen bemerkt, dass die Notwendigkeit eines Autos und der verschiedenen Versicherungen weder behauptet noch belegt ist, worauf bereits das Obergericht hingewiesen hat. Der anrechenbare Überschuss beträgt mithin sogar deutlich mehr als die vorinstanzlich angenommenen Fr. 1'685.80.
Im Übrigen sei festgehalten, dass der Beschwerdeführer weder Lohnausweise, Buchhaltungsunterlagen oder andere Belege für seine Einkünfte (welche die Beschwerdegegnerin auf Fr. 9'000.-- pro Monat beziffert) zu den Akten noch je über seine Vermögensverhältnisse Auskunft gegeben hat (die Beschwerdegegnerin verweist u.a. auf das Miteigentum an einer Liegenschaft in Bettys Bay). Sodann ist bereits darauf hingewiesen worden, dass offensichtlich nur eine von mehreren Seiten der Steuerveranlagung eingereicht worden ist und sich die Angaben zum Vermögen offenkundig auf einer Folgeseite befinden müssen. Auch angesichts dieser Weigerung, im Rahmen der Mitwirkungspflicht über die Einkommens- und Vermögensverhältnisse umfassend Auskunft zu geben und Unterlagen einzureichen, kann von einer Verletzung des verfassungsmässigen Anspruchs auf unentgeltliche Rechtspflege keine Rede sein (<ref-ruling> E. 3a S. 181 f).
Der angefochtene Entscheid hält in jeder Hinsicht vor <ref-law> stand.
5. Grundsätzlich ist das Rückführungsverfahren auch auf Bundesebene kostenlos (Art. 26 Abs. 2 HEntfÜ). Südafrika hat indes einen Vorbehalt angebracht, wonach die Verfahrens- und Parteikosten nur im Rahmen des Systems der unentgeltlichen Rechtspflege übernommen werden (Art. 26 Abs. 3 i.V.m. Art. 42 HEntfÜ). Die Schweiz wendet diesfalls das Prinzip der Gegenseitigkeit an (Art. 21 Abs. 1 lit. b des Wiener Übereinkommens über das Recht der Verträge, SR 0.111). Aufgrund der Ausführungen in E. 4 kann der Beschwerdeführer nicht als prozessarm gelten, weshalb er auch für das bundesgerichtliche Verfahren kosten- und entschädigungspflichtig wird (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in Zivilsachen wird abgewiesen.
2. Das Gesuch der Beschwerdeführers um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
4. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 4'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Kantonsgericht Basel-Landschaft schriftlich mitgeteilt.
Lausanne, 28. Februar 2008
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Raselli Möckli