Sachverhalt:
A. Der nigerianische Staatsangehörige X._ reiste am 17. Mai 2008 von London her kommend über den Flughafen Zürich-Kloten in die Schweiz ein. Am 19. Mai 2008 hielt ihn die Kantonspolizei Bern in Biel an und überprüfte seine Personalien näher. Sein Pass wurde dem Kriminaltechnischen Dienst (KTD) übergeben, welcher diesen als gefälscht betrachtete. In der Folge wies die Ausländerbehörde der Einwohnergemeinde Biel X._ formlos aus der Schweiz weg und am 19. Mai 2008 wurde er in Ausschaffungshaft versetzt; die Haftrichterin 2 des Haftgerichts III Bern-Mittelland bestätigte am 22. Mai 2008 die Haft. Am 5. Juni 2008 reiste X._ mit einem vom Bundesamt für Migration (BFM) ausgestellten "Laisser-Passer" nach London zurück.
Der a.o. Gerichtspräsident 13 des Gerichtskreises II Biel-Nidau hob am 19. November 2008 die gegen X._ wegen Fälschung von Ausweisen, Verletzung von Einreisebestimmungen und rechtswidrigen Aufenthalts eingeleitete Strafverfolgung auf. Am 8. Dezember 2008 widerrief das BFM das am 2. Juni 2008 gegenüber X._ angeordnete Einreiseverbot.
Am 16. Oktober 2008 ersuchte X._ den Kanton Bern um Schadenersatz (Fr. 112'706.--) und Genugtuung (Fr. 1'800.--) wegen ungerechtfertigter Ausschaffungshaft.
B. Mit Verfügung vom 17. Mai 2010 wies die Polizei- und Militärdirektion des Kantons Bern (POM) das Gesuch um Schadenersatz und Genugtuung vollumfänglich ab.
Dagegen erhob X._ Beschwerde beim Verwaltungsgericht des Kantons Bern und beantragte, es sei ihm ein Schadenersatz von Fr. 92'557.35 und eine Genugtuung von Fr. 1'800.--, jeweils nebst Zins, zu bezahlen. Zusätzlich machte er Kosten für die anwaltliche Vertretung in Grossbritannien und der Schweiz geltend. Das Verwaltungsgericht hiess mit Urteil vom 6. Dezember 2011 die Beschwerde teilweise gut und verpflichtete den Kanton Bern (POM), dem Beschwerdeführer eine Genugtuung von Fr. 1'800.-- zuzüglich 5 % Zins seit dem 5. Juni 2008 und für das Verfahren vor dem Haftgericht III Bern-Mittelland eine Entschädigung von Fr. 1'500.-- (inkl. Auslagen und MWSt) zu bezahlen. Im Übrigen wurde die Beschwerde abgewiesen ebenso das Gesuch um unentgeltliche Prozessführung, soweit es nicht gegenstandslos geworden war.
C. Mit Eingabe vom 30. Januar 2012 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht und beantragt das Urteil des Verwaltungsgerichts des Kantons Bern sei wie folgt "abzuändern": Bezüglich der Genugtuung von Fr. 1'800.-- und der Entschädigung für das Verfahren vor dem Haftgericht von Fr. 1'500.-- sei das Urteil zu bestätigen. Zudem sei der Kanton Bern zu verurteilen, dem Beschwerdeführer einen Schadenersatz in der Höhe von Fr. 90'652.50 (zuzüglich Zins zu 5 % seit dem 9. August 2008) zu bezahlen. Weiter wird die unentgeltliche Prozessführung für das Verfahren vor der Vorinstanz beantragt.
Mit separater Eingabe vom 23. Februar 2012 ersucht X._ um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren
Das Verwaltungsgericht und die Polizei- und Militärdirektion des Kantons Bern beantragen die Abweisung der Beschwerde. Das Bundesamt für Migration verzichtet auf eine Stellungnahme.

Erwägungen:
1. Ansprüche aus Staatshaftung gelten - mit Ausnahme der Fälle der Haftung für medizinische Tätigkeit (Art. 31 Abs. 1 lit. d des Reglements vom 20. November 2006 für das Bundesgericht [BGerR; SR 173.110.131]; <ref-ruling> E. 2.1 S. 465 f.) - als öffentlich-rechtlich und sind vor Bundesgericht daher mit Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) geltend zu machen. Zuständig ist innerhalb des Bundesgerichts die II. öffentlich-rechtliche Abteilung, ausser für Ansprüche aus strafprozessualen Normen über Entschädigungen, wofür die strafrechtliche Abteilung zuständig ist (Art. 30 Abs. 1 lit. c Ziff. 1 BGerR; <ref-ruling> E. 1.1.2 S. 46), und Ansprüche gestützt auf das Sozialversicherungsrecht, welche in der Zuständigkeit der sozialrechtlichen Abteilungen liegen (<ref-ruling>; <ref-ruling>; <ref-ruling>). Zu beachten ist sodann <ref-law>, wonach die Beschwerde in vermögensrechtlichen Angelegenheiten auf dem Gebiet der Staatshaftung unzulässig ist, wenn der Streitwert weniger als Fr. 30'000.-- beträgt. Im vorliegenden Fall ist der Streitwert indes höher und die Beschwerde in öffentlich-rechtlichen Angelegenheiten daher zulässig.
2. 2.1 Mit freier Kognition überprüft das Bundesgericht u.a. die richtige Anwendung von Bundesrecht, Völkerrecht und kantonalen verfassungsmässigen Rechten (Art. 95 lit. a - c BGG), aber - abgesehen von hier nicht in Betracht kommenden Fällen (Art. 95 lit. d und e BGG) - nicht diejenige des übrigen kantonalen Rechts; hier beschränkt sich die Überprüfungsbefugnis des Bundesgerichts darauf, ob durch die Anwendung kantonalen Rechts Bundesrecht oder Völkerrecht verletzt wird (<ref-law>), wobei namentlich die willkürliche Anwendung kantonalen Rechts in Betracht fällt. Das Bundesgericht prüft zudem die Verletzung von Grundrechten und von kantonalem Recht nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Der Beschwerdeführer hat anhand der Erwägungen des angefochtenen Entscheids klar und detailliert darzulegen, inwiefern verfassungsmässige Rechte verletzt worden sein sollen (<ref-ruling> E. 6 S. 397).
2.2 Das Bundesgericht stellt grundsätzlich auf den von der Vorinstanz festgestellten Sachverhalt ab (<ref-law>). Diese Sachverhaltsfeststellungen können vor Bundesgericht nur gerügt werden, wenn sie offensichtlich unrichtig - d.h. willkürlich - sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG).
3. 3.1 Der angefochtene Entscheid stützt sich einerseits auf kantonales Staatshaftungs- bzw. Verantwortlichkeitsrecht (Art. 100 ff. des Personalgesetzes [des Kantons Bern] vom 16. September 2004 [PG/BE; BSG 153.01] in Verbindung mit Art. 57 Abs. 1 des Polizeigesetzes [des Kantons Bern] vom 8. Juni 1997 [PolG/BE; BSG 551.1]). Gemäss Art. 100 Abs. 1 PG/BE haftet der Kanton für Schaden, den die Mitarbeiterinnen und Mitarbeiter und die nebenamtlich Tätigen in Ausübung ihrer amtlichen Tätigkeit Dritten widerrechtlich zugefügt haben. Für Verletzungen der körperlichen Integrität und schwere Persönlichkeitsverletzungen haben die Geschädigten Anspruch auf eine angemessene Genugtuung (Art. 100 Abs. 3 PG/BE). Andererseits hat sich die Vorinstanz auf Art. 25 Abs. 5 der Verfassung des Kantons Bern vom 6. Juni 1993 (KV/BE; SR 131.212) gestützt, wonach das Gemeinwesen der betroffenen Person vollen Ersatz des Schadens und allenfalls Genugtuung schuldet, wenn sich der Freiheitsentzug als widerrechtlich oder ungerechtfertigt erweist.
3.2 Die Vorinstanz hat erwogen, abgesehen von Zweifeln an der Echtheit des nigerianischen Passes des Beschwerdeführers habe nichts darauf hingedeutet, dass der Beschwerdeführer einer Wegweisung allenfalls nicht Folge leisten würde. Seine Ausreise sei rückwirkend betrachtet weder an den angeblich gefälschten Reisepapieren noch an seiner Weigerung, die Schweiz zu verlassen, gescheitert. Vielmehr sei anzunehmen, dass der Beschwerdeführer, wäre er nicht in Ausschaffungshaft genommen worden, noch am Tag seiner Festnahme den reservierten Flug angetreten hätte und freiwillig aus der Schweiz ausgereist wäre. Bei dieser Sachlage müsse die Haftanordnung jedenfalls als im Nachhinein betrachtet ungerechtfertigt bezeichnet werden (vgl. angefochtener Entscheid E. 3.3.3). Dementsprechend hat die Vorinstanz - gestützt auf Art. 25 Abs. 5 KV/BE - dem Beschwerdeführer, der sich vom 19. Mai bis 5. Juni 2008, also insgesamt während 18 Tagen, ungerechtfertigt in Ausschaffungshaft befand, eine Genugtuung in der Höhe von Fr. 1'800.-- (zuzüglich Zins zu 5 % seit dem 5. Juni 2008) zugesprochen (vgl. angefochtener Entscheid E. 3.4).
3.3 Hingegen hat die Vorinstanz das Begehren um Schadenersatz in Bezug auf den geltend gemachten Erwerbsausfall bzw. die Anwaltskosten in Grossbritannien und der Schweiz abgewiesen. Der Beschwerdeführer habe weder für seine Anstellung in Grossbritannien noch für die Höhe der Entlöhnung oder die angebliche Kündigung glaubwürdige Beweise beigebracht (vgl. angefochtener Entscheid E. 4.2.2). Zudem könne auch kein Schadenersatz für Erwerbsausfall zugesprochen werden, weil zwischen dem Verhalten der kantonalen Behörden und dem angeblich eingetretenen Schaden kein genügender Kausalzusammenhang bestehe (vgl. angefochtener Entscheid E. 4.2.3).
4. 4.1 Die angeordnete Haft war nicht nur ungerechtfertigt, sondern auch widerrechtlich, weil die Voraussetzungen der Haftanordnung nicht gegeben waren. Das löst die Schadenersatzpflicht des Gemeinwesens aus (Art. 5 Ziff. 5 EMRK). Die Schadenersatzpflicht anerkennt auch die Vorinstanz. Strittig ist nur noch, ob Schaden in Folge Erwerbsausfalls bzw. Kündigung durch den bisherigen Arbeitgeber entstanden ist. In Bezug auf die angeblich entstandenen Anwaltskosten in Grossbritannien und der Schweiz hat der Beschwerdeführer hingegen ausdrücklich auf einen Weiterzug verzichtet, da der finanzielle Aufwand letztlich unbewiesen bleibe und deshalb die diesbezüglichen Ausführungen der Vorinstanz weder Bundesrecht verletzten noch willkürlich seien (vgl. Beschwerdeschrift Ziff. 101 ff.).
4.2 Der Beschwerdeführer rügt im Zusammenhang mit dem beantragten Schadenersatz für entgangenes Einkommen im Wesentlichen nur eine offensichtlich unrichtige Feststellung des Sachverhalts bzw. eine willkürliche Beweiswürdigung durch die Vorinstanz. Hingegen erhebt der Beschwerdeführer keine weiteren Grundrechtsrügen (vgl. insbesondere Art. 25 Abs. 5 KV/BE oder Art. 5 Ziff. 5 EMRK betreffend), welche den Anforderungen von <ref-law> zu genügen vermögen (vgl. E. 2.1 hiervor). Insbesondere ist seinen Ausführungen nicht zu entnehmen, inwiefern das angefochtene Urteil verfassungsmässige Rechte des Beschwerdeführers verletzen soll.
4.3 Wie bereits erwähnt (vgl. E. 2.2 hiervor) legt das Bundesgericht seinem Urteil grundsätzlich den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Soweit die vorinstanzlichen Sachverhaltsfeststellungen beanstandet werden und eine mangelhafte Sachverhaltsfeststellung für den Ausgang des Verfahrens entscheidend ist, kann nur geltend gemacht werden, die Feststellungen seien offensichtlich unrichtig oder beruhten auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). Offensichtlich unrichtig bedeutet willkürlich (<ref-ruling> E. 2.4 S. 314 mit Hinweis). Auch bezüglich des Willkürverbots gilt dabei eine qualifizierte Rügepflicht (<ref-law>).
Zu prüfen ist demnach im Folgenden, ob die tatsächliche Feststellung der Vorinstanz, der Beschwerdegegner habe weder für seine Anstellung in Grossbritannien noch für die Höhe des angeblichen Erwerbsausfalls glaubwürdige Beweise erbracht, willkürlich ist.
4.3.1 Willkür im Sinne von <ref-law> liegt nach ständiger Rechtsprechung nicht schon dann vor, wenn das angefochtene Urteil nicht mit der Darstellung des Beschwerdeführers übereinstimmt oder eine andere Lösung oder Würdigung vertretbar erscheint oder gar vorzuziehen wäre, sondern nur, wenn der angefochtene Entscheid auf einer schlechterdings unhaltbaren oder widersprüchlichen Beweiswürdigung beruht, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 2.4 S. 5).
4.3.2 Die Vorinstanz hat im angefochtenen Entscheid unter anderem festgestellt, dass das vom Beschwerdeführer eingereichte Kündigungsschreiben der "Microsystems International (OK) Ltd." vom 23. Mai 2008 auf dem gleichen Briefpapier gedruckt worden ist, wie die erste Seite eines Schreibens vom 20. April 2009, das angeblich von der Anwaltskanzlei Edward Leonards Solicitors stammen soll. Die Vorinstanz durfte daraus ohne in Willkür zu verfallen den Schluss ziehen, dass die beiden Dokumente vom selben Urheber stammen (vgl. angefochtener Entscheid E. 4.2.2), dies umso mehr, als die beiden Dokumente auch noch genau den gleichen Schrifttyp aufweisen. Weiter hat die Vorinstanz festgestellt, dass ein Widerspruch besteht zwischen dem Datum der angeblichen Kündigung vom 23. Mai 2008 und dem im Fragebogen vom 6. September 2008 angegebenen Kündigungsgrund, wonach der Beschwerdeführer während dreier Wochen unentschuldigt nicht zur Arbeit erschienen sei. Zudem hat die Vorinstanz festgestellt, dass der Beschwerdeführer während seiner rund dreiwöchigen Haft seinen Arbeitgeber nie kontaktiert hat. Aufgrund dieser Feststellungen und diverser weiterer Unstimmigkeiten und Ungereimtheiten (vgl. dazu auch die Abklärungen der Schweizerischen Botschaft in London im angefochtenen Entscheid E. 4.2.1 [betreffend Erwerbsausfall] bzw. E. 4.3 [betreffend Anwaltskosten in Grossbritannien]) durfte die Vorinstanz den Schluss ziehen, der Beschwerdeführer vermöge weder für seine Anstellung bei der Microsystems noch für die Höhe der Entschädigung oder die angebliche Kündigung glaubwürdige Beweise beizubringen, womit der geltend gemachte Erwerbsausfall unbewiesen bleibe. Die weitgehend rein appellatorische Kritik des Beschwerdeführers lässt diese Feststellung nicht als willkürlich erscheinen. Insbesondere löst auch das Schreiben der Microsystems International Ltd. vom 9. November 2009 den Widerspruch nicht auf, dass am 23. Mai 2008, also vier Tage nach der Verhaftung, die ''Termination'' ausgesprochen wurde, und im Fragebogen vom 6. September 2008 als Grund für die Vertragsauflösung angegeben wurde, der Beschwerdeführer sei drei Wochen grundlos ferngeblieben. Daraus folgt weiter, dass die Vorinstanz bereits mangels Nachweises eines tatsächlich relevanten materiellen Schadens die Schadenersatzpflicht verneinen durfte (vgl. <ref-ruling> E. 2 S. 142), so dass sich eine nähere Prüfung der Frage des genügenden Kausalzusammenhangs (vgl. angefochtener Entscheid E. 4.2.3) hier erübrigt.
Daraus folgt, dass die Vorinstanz im angefochtenen Entscheid weder eine willkürliche Beweiswürdigung vorgenommen hat noch Beweislastregeln des Bundesrechts verletzt hat.
5. Nach der Rechtsprechung sind Prozessbegehren aussichtslos, deren Gewinnaussichten beträchtlich geringer sind als die Verlustgefahren und die deshalb kaum als ernsthaft bezeichnet werden können. Massgeblich ist, ob sich eine vernünftige, nicht mittellose Partei ebenfalls zur Beschwerde entschlossen hätte. Eine Partei soll einen Prozess, den sie auf eigene Rechnung und Gefahr nicht führen würde, nicht deshalb anstrengen können, weil er sie nichts kostet (<ref-ruling> E. 2.3.1 S. 135 f. mit Hinweisen).
Wie sich aus den vorstehenden Erwägungen ergibt, durfte das Verwaltungsgericht vorliegend die Voraussetzungen für eine Schadenersatzpflicht des Kantons zulässigerweise verneinen; der Beschwerdeführer konnte dabei nicht ernsthaft mit einer Gutheissung seiner Anträge (bezüglich Schadenersatz) rechnen. Die unentgeltliche Rechtspflege und Verbeiständung wurde ihm vom Verwaltungsgericht daher zu Recht verweigert, soweit das Gesuch durch die teilweise Gutheissung ohnehin nicht gegenstandslos geworden war.
6. Die Beschwerde erweist sich nach dem Gesagten als unbegründet und ist abzuweisen. Entsprechend würde der Beschwerdeführer kostenpflichtig (Art. 66 Abs. 1 erster Satz BGG), zumal seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung - das im Übrigen erst nach Einreichen der Beschwerde gestellt wurde - aus denselben, in E. 5 genannten Überlegungen auch im bundesgerichtlichen Verfahren nicht entsprochen werden kann (vgl. <ref-law>). Indessen rechtfertigen es die Umstände, auf die Erhebung von Kosten zu verzichten (Art. 66 Abs. 1 zweiter Satz BGG).
Der obsiegende Kanton Bern hat keinen Anspruch auf Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Es werden keine Kosten erhoben, und es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird dem Beschwerdeführer, der Polizei- und Militärdirektion, dem Verwaltungsgericht des Kantons Bern und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 14. August 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger