Sachverhalt: A. Der aus dem Kosovo stammende X._ (geb. 1955) reiste am 21. März 1981 in die Schweiz ein und heiratete im selben Jahr die Schweizer Bürgerin B.B._. Seit dem 7. November 2001 ist er im Besitz der Niederlassungsbewilligung. Der gemeinsame Sohn C.B._ wurde am 27. März 2002 geboren. X._ trat mehrfach strafrechtlich in Erscheinung und wurde wie folgt verurteilt: am 13. Mai 1983 vom Strafamtsgericht Thun wegen fahrlässiger Körperverletzung mit schwerer Schädigung zu einer Gefängnisstrafe von sieben Monaten, am 29. Januar 1987 vom Obergericht des Kantons Bern wegen Raufhandels zu fünf Monaten Gefängnis, am 7. Juli 1993 durch den Gerichtspräsidenten Wimmis wegen einfacher Körperverletzung mit gefährlichem Gegenstand, fahrlässigen Fahrens in angetrunkenem Zustand und Führens eines Personenwagens ohne Licht zu zwei Monaten Gefängnis, am 28. Juli 1993 durch den Gerichtspräsidenten Niedersimmental wegen unerlaubten Waffenerwerbs und -besitzes mit einer Busse von Fr. 200.--, am 28. Februar 2001 durch den Gerichtspräsidenten 6 des Gerichtskreises X Thun wegen einfacher Körperverletzung mit gefährlichem Gegenstand (Messer) zu 2 Monaten Gefängnis. Am 10. Dezember 2004 - also im Alter von bereits 49 Jahren - wurde X._ in einem Club in E._ - nach einer zunächst verbalen Auseinandersetzung - von ca. fünf bis sechs Personen mit Billardqueues und Stühlen angegriffen und durch einen heftigen Schlag auf den Hinterkopf verletzt. Er fuhr daraufhin zu seiner Wohnung in Spiez, wo er seine Wunde verarztete, eine Pistole behändigte und zum Club zurückfuhr. Dort wollte O.D._ von ihm wissen, was vorher vorgefallen war. X._ verweigerte diese Informationen ("lass mich in Ruhe"), worauf O.D._ einen verdeckt mitgeführten Revolver zückte und X._ damit auf den bereits lädierten Kopf schlug. X._ nahm in der Folge seinerseits die Pistole hervor und schoss zwei Mal "sehenden Auges" aus einer Distanz von weniger als 40 cm auf O.D._. Er traf diesen im Brustkorb und am streckseitigen Unterarm. O.D._ starb an den Folgen der Schussverletzungen. B. Mit Urteil des Kreisgerichts Thun vom 22. September 2006 wurde X._ von der Anschuldigung der vorsätzlichen Tötung wegen Notwehr freigesprochen. Auf Appellation der Staatsanwaltschaft und der Privatkläger sprach das Obergericht des Kantons Bern X._ mit Urteil vom 25. Oktober 2007 der vorsätzlichen Tötung, begangen im Notwehrexzess, schuldig und verurteilte ihn zu sechs Jahren Freiheitsstrafe. Eine hiegegen gerichtete Beschwerde hiess das Bundesgericht teilweise gut (Urteil 6B_15/2008 vom 2. September 2008) und wies die Sache an das Obergericht zurück. Dieses bestätigte mit Urteil vom 12. Februar 2009 den Schuldspruch wegen vorsätzlicher Tötung, reduzierte jedoch die Freiheitsstrafe auf viereinhalb Jahre. Die hiegegen erneut erhobene Beschwerde wies das Bundesgericht am 5. November 2009 ab, soweit es darauf eintrat (Verfahren 6B_480/2009). X._ befand sich ab 11. Januar 2010 im Strafvollzug und wurde nach Verbüssen von zwei Dritteln der Strafe bedingt entlassen. C. Mit Verfügung vom 21. Dezember 2010 widerrief das Amt für Migration und Personenstand des Kantons Bern die Niederlassungsbewilligung von X._ und wies diesen aus der Schweiz weg. Eine hiegegen erhobene Beschwerde hiess die kantonale Polizei- und Militärdirektion am 16. Februar 2012 hinsichtlich der Gewährung der unentgeltlichen Rechtsverbeiständung gut; im Übrigen wies die Direktion die Beschwerde ab. D. Mit Urteil vom 9. Januar 2013 wies das Verwaltungsgericht des Kantons Bern die gegen den Direktionsentscheid gerichtete Beschwerde ab, soweit es darauf eintrat (Ziff. 1 des Urteilsdispositivs). Sodann überwies es die Akten an das Amt für Migration und Personenstand des Kantons Bern (Migrationsdienst), "damit dieses beim Bundesamt für Migration die Einleitung des Verfahrens auf vorläufige Aufnahme von X._ veranlasse" (Ziff. 2 des Urteilsdispositivs). Ausgangsgemäss auferlegte das Verwaltungsgericht X._ die Gerichtskosten (Ziff. 4 des Urteilsdispositivs), gewährte ihm aber die unentgeltliche Prozessführung (Ziff. 3 des Urteilsdispositivs). E. Mit Eingabe vom 6. Februar 2013 führt X._ "öffentlich-rechtliche Beschwerde" beim Bundesgericht mit den Anträgen, Ziff. 1 und 4 des letztgenannten Urteils aufzuheben und ihm - dem Beschwerdeführer - die Niederlassungsbewilligung nicht zu "entziehen" (recte: zu widerrufen); eventuell sei die Angelegenheit "zur Durchführung einer öffentlichen Verhandlung mit Anhörung des Beschwerdeführers und neuen Entscheidung an die Vorinstanz zurückzuweisen". Die Polizei- und Militärdirektion des Kantons Bern, das Verwaltungsgericht des Kantons Bern sowie das Bundesamt für Migration beantragen Abweisung der Beschwerde. Mit Eingabe vom 3. Juni 2013 hielt X._ an seinen Anträgen fest. F. Mit Verfügung vom 8. Juli 2013 erteilte der Instruktionsrichter der Beschwerde im Sinne der Erwägungen aufschiebende Wirkung. 