Sachverhalt: A. A._ (geboren am 20. Februar 1979) ist türkischer Staatsbürger. Er reiste am 15. Dezember 1999 in die Schweiz ein, worauf ihm am 1. Dezember 2000 unter Anerkennung der Flüchtlingseigenschaft Asyl gewährt wurde. Nach fünf Jahren erhielt er die Niederlassungsbewilligung. Am 5. August 2011 wies das Bundesgericht (Verfahren 6B_177/2011) eine Beschwerde von A._ gegen ein Urteil des Obergerichts Bern vom 19. November 2010 ab, mit dem A._ zweitinstanzlich wegen vorsätzlicher Tötung und Fahrens in fahrunfähigem Zustand zu einer Freiheitsstrafe von acht Jahren verurteilt wurde. Infolge dieser Verurteilung widerrief das Bundesamt für Migration (heute: Staatssekretariat für Migration) am 8. Dezember 2011 das A._ gewährte Asyl. A._ wurde am 23. August 2013 bedingt aus dem Strafvollzug entlassen; die Reststrafe belief sich auf 2 Jahre und acht Monate. Mit Verfügung vom 11. Oktober 2013 widerrief die Einwohnergemeinde Bern (heute: Einwohnerdienste, Migration und Fremdenpolizei der Stadt Bern) die Niederlassungsbewilligung von A._, wies ihn aus der Schweiz weg und setzte eine Ausreisefrist an. Im April 2014 heiratete A._ eine niederlassungsberechtigte türkische Staatsbürgerin, mit welcher er eine gemeinsame Tochter im Kleinkindalter hat. Am 19. November 2014 lehnte die Ausländerbehörde des Kantons Waadt einen Kantonswechsel bzw. die Erteilung einer Aufenthaltsbewilligung an A._ ab. B. Mit Entscheid vom 17. November 2014 wies die Polizei- und Militärdirektion des Kantons Bern die von A._ gegen die Verfügung vom 11. Oktober 2013 erhobene Beschwerde ab. Die Direktion ordnete an, die Akten seien an das Bundesamt für Migration (heute: Staatssekretariat für Migration) zur flüchtlingsrechtlichen Neubestimmung des Status des Beschwerdeführers und gegebenenfalls zur Durchführung eines Verfahrens auf vorläufige Aufnahme zu überweisen. Mit Urteil vom 27. Januar 2016 wies das Verwaltungsgericht des Kantons Bern eine von A._ dagegen geführte Beschwerde ab, bestätigte die angeordnete Aktenüberweisung und stellte fest, die erstinstanzlich auf Strafende (23. April 2016) festgesetzte Ausreisefrist gelte als aufgehoben. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 2. März 2016 an das Bundesgericht beantragt A._, das Urteil des Verwaltungsgerichts des Kantons Bern vom 27. Januar 2016, mit welchem der Beschwerdeentscheid der Polizei- und Militärdirektion des Kantons Bern vom 17. November und damit der von der Einwohnergemeinde Bern verfügte Widerruf der Niederlassungsbewilligung und die Wegweisung des Beschwerdeführers aus der Schweiz vom 11. Oktober 2013 bestätigt wurden, sei kostenfällig aufzuheben, und zur Verlegung des vorinstanzlichen Kostenentscheids an die Vorinstanz zurückzuweisen. Mit Eingabe vom 7. April 2016 ersucht der Beschwerdeführer um Gewährung der unentgeltlichen Rechtspflege. Die Einwohnerdienste, Migration und Fremdenpolizei der Stadt Bern sowie die Polizei- und Militärdirektion des Kantons Bern, die Vorinstanz und das SEM schliessen auf bzw. beantragen die (kostenfällige) Abweisung der Beschwerde. In einer weiteren Eingabe hält der Beschwerdeführer vollumfänglich an seiner Beschwerdebegründung fest.