Sachverhalt:
A. Der mutmasslich nigerianische Staatsangehörige X._ ersuchte am 21. April 2008 um Asyl in der Schweiz. Mit Entscheid vom 22. Mai 2008 trat das Bundesamt für Migration (BFM) auf das Asylgesuch nicht ein und wies X._ aus der Schweiz weg. Am 6. August 2008 wurde er vom Amt für Migration des Kantons Basel-Landschaft (AfM) in Ausschaffungshaft genommen. Das Kantonsgericht Basel-Landschaft, Abteilung Verfassungs- und Verwaltungsrecht, Einzelrichter für Zwangsmassnahmen im Ausländerrecht (Kantonsgericht) bestätigte diese Massnahme mit Urteil vom 8. August 2008 für eine Dauer von drei Monaten.
B. Auf Antrag des AfM verlängerte das Kantonsgericht die gegen X._ angeordnete Ausschaffungshaft am 5. November 2008, am 5. Februar 2009, am 5. Mai 2009 und am 4. August 2009 um jeweils drei weitere Monate. Diese Entscheide wurden von X._ nicht angefochten und erwuchsen in Rechtskraft. Am 3. November 2009 verfügte das Kantonsgericht erneut eine Verlängerung der Ausschaffungshaft um drei Monate.
C. Hiergegen führt X._ mit Eingabe vom 5. Dezember 2009 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Er beantragt die Aufhebung des angefochtenen Urteils und die Entlassung aus der Ausschaffungshaft.
D. Das AfM schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das BFM liess sich innert Frist nicht vernehmen und das Kantonsgericht verzichtet ausdrücklich auf eine Vernehmlassung. Mit Eingabe vom 26. Dezember 2009 nimmt X._ zum Vernehmlassungsergebnis Stellung.
E. Mit Verfügung vom 10. Dezember 2009 lehnte der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts das Gesuch von X._ ab, mit welchem dieser seine sofortige Haftentlassung als vorsorgliche Massnahme beantragt hatte.

Erwägungen:
1. 1.1 Die Beschwerde wurde unter Einhaltung der gesetzlichen Frist (Art. 100 Abs. 1 BGG) von einer durch die Entscheidung besonders berührten Partei mit einem schutzwürdigen Interesse an deren Aufhebung oder Änderung (Art. 89 Abs. 1 BGG) eingereicht. Sie richtet sich gegen einen von einer letzten kantonalen Instanz (Art. 86 Abs. 1 lit. d BGG) gefällten Endentscheid (Art. 90 BGG) in einer Angelegenheit des öffentlichen Rechts (Art. 82 lit. a BGG). Keiner der in Art. 83 BGG erwähnten Ausschlussgründe trifft zu. Auf die Beschwerde kann daher grundsätzlich eingetreten werden (unter Vorbehalt von E. 1.3 hiernach).
1.2 Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen.
1.3 Gemäss Art. 42 Abs. 1 BGG hat die Rechtsschrift die Begehren und deren Begründung zu enthalten. In der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (Art. 42 Abs. 2 BGG). Die Vorbringen müssen sachbezogen sein, damit aus der Beschwerdeschrift ersichtlich ist, in welchen Punkten und weshalb der angefochtene Entscheid beanstandet wird. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheides auseinandersetzt (<ref-ruling>). Eine qualifizierte Rügepflicht gilt u.a. hinsichtlich der Verletzung von Grundrechten: Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG; <ref-ruling> E. 1.4.2 S. 254).
2. Das Kantonsgericht stützte sich bei der Bestätigung und den Verlängerungen der Ausschaffungshaft jeweils auf Art. 76 Abs. 1 lit. b Ziff. 3 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20). Gemäss dieser Bestimmung kann die zuständige Behörde die betroffene ausländische Person zur Sicherstellung des Wegweisungsvollzugs in Haft nehmen, wenn sie ihrer Mitwirkungspflicht nach Art. 90 AuG sowie Art. 8 Abs. 1 lit. a oder Art. 8 Abs. 4 des Asylgesetzes vom 26. Juni 1998 (AsylG; SR 142.31) nicht nachkommt. Art. 90 AuG besagt, dass die Ausländerinnen und Ausländer verpflichtet sind, zutreffende und vollständige Angaben über die für die Regelung des Aufenthalts wesentlichen Tatsachen zu machen (lit. a), die erforderlichen Beweismittel unverzüglich einzureichen oder sich darum zu bemühen, sie innerhalb einer angemessenen Frist zu beschaffen (lit. b) und Ausweispapiere zu beschaffen oder bei deren Beschaffung durch die Behörden mitzuwirken (lit. c). Gemäss Art. 8 Abs. 1 lit. a AsylG sind Asylsuchende verpflichtet, an der Feststellung des Sachverhaltes mitzuwirken und insbesondere ihre Identität offen zu legen. Art. 8 Abs. 4 AsylG statuiert darüber hinaus die Verpflichtung, nach Vorliegen eines vollziehbaren Wegweisungsentscheides bei der Beschaffung gültiger Reisepapiere mitzuwirken.
Im angefochtenen Entscheid führt die Vorinstanz aus, der Beschwerdeführer habe diese Mitwirkungspflichten verletzt: Im ersten Herkunftsgespräch im September 2008 habe er angegeben, aus Kamerun zu stammen. Anlässlich seiner Anhörung durch die kamerunischen Behörden am 2. Dezember 2008 habe er sich jedoch geweigert, Englisch zu sprechen und behauptet, er sei nur der arabischen Sprache mächtig. Als Folge hiervon sei der Beschwerdeführer nicht als Staatsangehöriger von Kamerun anerkannt worden. Später habe er dann zugegeben, dass er nicht aus Kamerun stamme. Ein am 27. Oktober 2009 durchgeführtes zweites Herkunftsgespräch habe ergeben, dass der Beschwerdeführer aus Nigeria komme, zumal Sprache und Physiognomie für einen Nigerianer typisch seien. Der Beschwerdeführer habe sich jedoch geweigert, Fragen über Nigeria zu beantworten und geltend gemacht, er stamme in Wirklichkeit aus einem Land, welches in der Schweiz keine Botschaft habe. Anlässlich der Parteiverhandlung vom 3. November 2009 habe er dann wiederum behauptet, dass er aus Kamerun stamme und ausschliesslich Englisch spreche, nachdem bis zu diesem Zeitpunkt sämtliche Verhandlungen vor dem Einzelrichter des Kantonsgerichts unter Beizug eines Dolmetschers für die französische Sprache geführt worden seien. Mithin verhalte sich der Beschwerdeführer völlig unkooperativ, mache widersprüchliche Angaben und widersetze sich generell sämtlichen Versuchen, seine Herkunft zu ermitteln. Auch um eine selbständige Beschaffung von Reisepapieren habe er sich bis heute nicht bemüht.
3. Der Beschwerdeführer stellt diese Vorwürfe nicht in Abrede. In seiner Beschwerde beschränkt er sich vielmehr auf die Behauptung, das AfM sei der in Art. 76 Abs. 4 AuG statuierten Verpflichtung, die für den Vollzug der Weg- oder Ausweisung notwendigen Vorkehren umgehend zu treffen, nicht hinreichend nachgekommen: Zwischen dem 4. bzw. 9. März 2009 und dem 27. Oktober 2009 habe keine (zweite) Herkunftsanalyse stattgefunden, was einzig der mangelhaften Koordination zwischen dem AfM und dem BFM sowie der verzögerten Umsetzung dieser Abklärung durch die beiden Ämter zuzuschreiben sei. So habe das BFM dem AfM erst am 15. Juli 2009, d.h. vier Monate nachdem der Beschwerdeführer am 9. März 2009 der nigerianischen Botschaft zugeführt worden sei, mitgeteilt, welchen Experten das AfM für die Herkunftsabklärung organisieren solle. Das AfM seinerseits habe sich erst am 4. August 2009 nach der Verfügbarkeit des Experten erkundigt und dem BFM schliesslich mitgeteilt, dass dieser nicht abkömmlich sei. Danach sei es wiederum rund zehn Wochen gegangen, bis das BFM einen Ersatz vorgeschlagen habe und erst am 27. Oktober 2009 sei schliesslich das zweite Herkunftsgespräch durchgeführt worden. Nebst einer Widerhandlung gegen Art. 76 Abs. 4 AuG sieht der Beschwerdeführer im Verhalten der Migrationsbehörden auch eine Verletzung des in Art. 36 Abs. 3 BV verankerten Grundsatzes, wonach Eingriffe in Grundrechte stets verhältnismässig sein müssen und er rügt sinngemäss, dass sich das angefochtene Urteil mit dieser Frage nicht auseinandersetze. Sodann werden vom Beschwerdeführer in diesem Zusammenhang Art. 10 Abs. 2 BV (Grundrecht auf persönliche Freiheit) sowie Art. 31 BV (Rechte bei Freiheitsentzug) angerufen, und er verweist ferner auf den Inhalt der EU-Rückführungsrichtlinie.
4. Soweit der Beschwerdeführer eine Verletzung des Beschleunigungsgebotes von Art. 76 Abs. 4 AuG in der Zeit vor dem 4. August 2009 behauptet, erweist sich seine Rüge als unzulässig: Die Rechtmässigkeit der Ausschaffungshaft bis zu diesem Zeitpunkt bildete bereits Gegenstand der Urteile des Kantonsgerichts vom 8. August 2008, 5. November 2008, 5. Februar 2009, 5. Mai 2009 und 4. August 2009, welche vom Beschwerdeführer - wie bereits ausgeführt - jeweils nicht angefochten wurden. Die Rechtskraft dieser Entscheide steht einer erneuten Überprüfung des Verhaltens des AfM bzw. BFM während dieser Periode entgegen.
Demzufolge kann im vorliegenden Verfahren nur von Bedeutung sein, ob das Beschleunigungsgebot in der Zeit vom 4. August 2009 bis zur angefochtenen Haftverlängerung am 3. November 2009 verletzt worden ist. Wie die Vorinstanz zutreffend ausgeführt hat, ist in der Regel von einer Verletzung des Beschleunigungsgebotes auszugehen, wenn während mehr als zwei Monaten keinerlei Vorkehren mehr im Hinblick auf die Ausschaffung getroffen wurden, ohne dass diese Verzögerung in erster Linie auf das Verhalten ausländischer Behörden oder des Betroffenen selber zurückgeht. Entscheidend sind jedoch die Umstände des Einzelfalls, wobei ein widersprüchliches Verhalten des Betroffenen mitberücksichtigt werden kann (<ref-ruling> E. 3a S. 51 mit Hinweisen).
Wie den Akten zu entnehmen ist, wurde das BFM am 4. August 2009 vom AfM davon in Kenntnis gesetzt, dass der bisher für das zweite Herkunftsgespräch mit dem Beschwerdeführer vorgesehene Experte innert nützlicher Frist nicht verfügbar sei. Das AfM ersuchte daher um Alternativvorschläge, insbesondere um Benennung eines anderen Herkunftsspezialisten. Am 19. August 2009 erfolgte ein Haftbesuch des AfM beim Beschwerdeführer, welcher bei dieser Gelegenheit nochmals hervorhob, dass er nicht heimkehren wolle und selber auch nichts in dieser Hinsicht unternommen habe. Am 14. Oktober 2009 fand eine telefonische Besprechung zwischen AfM und BFM statt, worauf das BFM am 19. Oktober 2009 zwei weitere Herkunftsspezialisten vorschlug und das AfM am 27. Oktober 2009 eine weitere Anhörung organisierte.
In der vorliegend massgeblichen Periode haben die Migrationsbehörden somit durchaus geeignete Massnahmen vorbereitet und umgesetzt, welche auf Feststellung der Nationalität des Beschwerdeführers und damit auf die Durchführbarkeit der geplanten Ausschaffung abzielten. Eine Untätigkeit während mehr als zwei Monaten liegt nicht vor. Zwar ist richtig, dass ein Grossteil der Aktivitäten von AfM und BFM dazu dienten, Ersatz für den nicht verfügbaren Herkunftsspezialisten zu organisieren, und es trifft ebenfalls zu, dass der Ausfall des ursprünglich vorgesehenen Experten nicht vom Beschwerdeführer verschuldet wurde. Dass überhaupt ein zweites Herkunftsgespräch durchgeführt werden musste, ist jedoch sehr wohl vom Beschwerdeführer zu verantworten: Durch seine widersprüchlichen Angaben zu Herkunft und Sprache führte er die Behörden absichtlich in die Irre und nahm offenkundig in Kauf, dass das ursprüngliche Herkunftsgespräch zu einem falschen Ergebnis führte. Aus den genannten Gründen ergibt sich, dass die von den Migrationsbehörden in der hier massgeblichen Zeitspanne vom 4. August 2009 bis 3. November 2009 vorgenommenen Bemühungen den Anforderungen des Beschleunigungsgebotes genügen und somit keine Verletzung von Art. 76 Abs. 4 AuG vorliegt.
5. Ins Leere gehen die Rügen des Beschwerdeführers auch insoweit, als er die Verhältnismässigkeit der Haftverlängerung bezweifelt und überdies einwendet, das Kantonsgericht habe sich mit dieser Frage nicht auseinandergesetzt. Wie vom AfM in dessen Vernehmlassung zutreffend bemerkt wurde, hat die Vorinstanz sehr wohl eine Verhältnismässigkeitsprüfung vorgenommen:
In E. 8 des angefochtenen Entscheids hat das Kantonsgericht hierzu in nachvollziehbarer Weise ausgeführt, dass aufgrund des bisherigen Verhaltens des Beschwerdeführers nicht angenommen werden könne, dass sich dieser im Falle einer Haftentlassung unverzüglich und ernsthaft um die Beschaffung seiner Reisepapiere bemühen und sich zu gegebener Zeit den Behörden zur Verfügung halten werde. Die Ausschaffungshaft stelle daher die einzige geeignete Massnahme dar, mit welcher der Vollzug der Wegweisung sichergestellt werden könne. Da die definitive Klärung seiner Identität und die Beschaffung der Reisepapiere voraussichtlich noch einige Zeit in Anspruch nehme, sei auch die dreimonatige Dauer der Haftverlängerung erforderlich.
Zu diesen Erwägungen des Kantonsgerichts äussert sich der Beschwerdeführer nicht einmal ansatzweise und er zeigt insbesondere nicht auf, inwiefern hierdurch seine Rechte verletzt worden seien. Diesbezüglich kommt der Beschwerdeführer mithin seiner Begründungspflicht nicht nach, und die Beschwerde erweist sich in diesem Umfang als unsubstantiiert (vgl. E. 1.3).
Nichts anderes gilt bezüglich der vom Beschwerdeführer ebenfalls gerügten Verletzung des verfassungsmässigen Rechts auf persönliche Freiheit sowie der garantierten Rechte bei Freiheitsentzug: Auch diesfalls verzichtet der Beschwerdeführer auf eine Begründung seiner Rüge und beschränkt sich stattdessen auf eine pauschale Behauptung.
6. Der Verweis des Beschwerdeführers auf die Richtlinie 2008/115/EG des Europäischen Parlaments und des Rates vom 16. Dezember 2008 über gemeinsame Normen und Verfahren in den Mitgliedstaaten zur Rückführung illegal aufhältiger Drittstaatsangehöriger (vgl. Amtsblatt der Europäischen Union 2008 L 348 vom 24. Dezember 2008 S. 98 ff.) erweist sich ebenfalls als unbehelflich: Diese sog. EU-Rückführungsrichtlinie wurde von der Schweiz noch nicht umgesetzt, worauf das AfM richtigerweise hingewiesen hat. Im Übrigen lässt auch diese Richtlinie eine Abschiebehaft von bis zu 18 Monaten zu, falls der Betroffene - wie im vorliegenden Fall - nicht kooperiert; diese Maximaldauer wird durch die hier angefochtene Entscheidung des Kantonsgerichts nicht überschritten.
7. Nach dem Ausgeführten erweist sich die Beschwerde in öffentlich-rechtlichen Angelegenheiten als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
Dem Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege im bundesgerichtlichen Verfahren kann nicht entsprochen werden, da die Beschwerde von vornherein als aussichtslos erschien (Art. 64 Abs. 1 BGG e contrario). Aufgrund der Umstände, insbesondere der völligen Mittellosigkeit des Beschwerdeführers, wird indes auf die Erhebung von Gerichtskosten verzichtet (Art. 66 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege im bundesgerichtlichen Verfahren wird abgewiesen.
3. Auf die Erhebung von Gerichtskosten wird verzichtet.
4. Dieses Urteil wird dem Beschwerdeführer, dem Amt für Migration Basel-Landschaft, dem Kantonsgericht Basel-Landschaft, Abteilung Verfassungs- und Verwaltungsrecht, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 11. Januar 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Zähndler