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. 