Sachverhalt: A. Der aus Mazedonien stammende X._ (geb. 1978) heiratete im März 2004 in seiner Heimat die Schweizer Bürgerin Y._ (geb. 1969), welche zwei eigene Kinder (A._, geb. 1992 und B._, geb. 1997) mit in die Ehe brachte. Y._, die stark sehbehindert ist und nach der Eheschliessung eine von der eidgenössischen Invalidenversicherung bezahlte Umschulung zur medizinischen Masseurin begann, zog ihren Ehemann in der Folge in die Schweiz nach (Einreise am 12. Mai 2004), wo er eine Aufenthaltsbewilligung erhielt, welche regelmässig verlängert wurde (zuletzt bis zum 20. Oktober 2007). X._ arbeitete als Gerüstbauer, war aber zwischenzeitlich arbeitslos und kam seinen finanziellen Verpflichtungen nicht nach; zahlreiche Betreibungen waren die Folge. B. Bereits zwischen Mai 2006 und Januar 2007 war der gemeinsame Haushalt der Eheleute X._ - Y._ aufgehoben. Die Ehefrau hatte ihren Mann wegen häuslicher Gewalt angezeigt, die Anzeige später aber wieder zurückgezogen. Seit August 2007 leben die beiden erneut getrennt. Nachdem Y._ ein Eheschutzverfahren eingeleitet hatte, verfügte die Gerichtspräsidentin 2 der Zivilabteilung des Gerichtskreises VIII Bern-Laupen am 26. September 2007 gegenüber X._ ein Verbot, mit seiner Ehefrau Kontakt aufzunehmen. Am 11. Januar 2008 unterzeichneten die Eheleute eine förmliche Trennungsvereinbarung, welche gerichtlich genehmigt wurde. C. Wenige Wochen vorher, am 6. Dezember 2007, hatten die Einwohnerdienste der Stadt Bern (Migration und Fremdenpolizei) die Aufenthaltsbewilligung von X._ aufgrund der Vorkommnisse in der Ehe nicht mehr verlängert und ihm eine Ausreisefrist angesetzt. Zuvor hatten die zuständigen Dienste der Ehefrau schriftlich einen Fragenkatalog unterbreitet. Nach Eingang der Antworten setzten die Einwohnerdienste X._ Frist zur Stellungnahme an, welch letztere dieser - inzwischen anwaltlich verbeiständet - mit Eingabe vom 30. November 2007 einreichte. Ohne die dort dargelegten Einwände explizit zu würdigen, kamen die Einwohnerdienste in ihrer Verfügung vom 6. Dezember 2007 zum Schluss, X._ berufe sich aus rein fremdenpolizeilichen Überlegungen und damit rechtsmissbräuchlich auf seine bloss noch formell bestehende Ehe, weshalb die Aufenthaltsbewilligung nicht mehr zu verlängern sei. D. Hiegegen erhob X._ mit Eingabe vom 9. Januar 2008 Beschwerde bei der Polizei- und Militärdirektion des Kantons Bern und machte einen Rechtsanspruch auf eine Aufenthaltsbewilligung geltend. Nach der Durchführung eines umfassenden Beweisverfahrens, worin Y._ u.a. schriftlich bekräftigt hatte, mit einer Wiederaufnahme der ehelichen Gemeinschaft sei nicht mehr zu rechnen (was X._ umgehend bestritt, weil bei seiner Frau "Besuche über das Wochenende (...) wieder möglich" seien), kam die Polizei- und Militärdirektion des Kantons Bern in ihrem Beschwerdeentscheid vom 8. August 2008 zum Schluss, die Einwohnerdienste der Stadt Bern hätten beim Erlass ihrer Verfügung vom 6. Dezember 2007 mangels Auseinandersetzung mit den vorgetragenen Argumenten zwar das rechtliche Gehör von X._ verletzt; diese Gehörsverletzung könne aber als geheilt betrachtet werden. Weiter erwog die Direktion, ein Rechtsanspruch auf Bewilligungserneuerung sei klarerweise nicht (mehr) vorhanden; und eine Ermessensbewilligung sei mangels eines entsprechenden Antrags nicht Gegenstand des Verfahrens. Aus diesen Gründen wies die Direktion die Beschwerde ab. E. X._ gelangte hiegegen an das Verwaltungsgericht des Kantons Bern. Im Rahmen der Instruktion dieses Beschwerdeverfahrens reichte er dem Gericht als neues Beweismittel eine Liste der via Telekommunikation bei ihm eingegangenen SMS-Nachrichten ("Short Message Services") seiner Ehefrau ein, die diese ihm in der Zeit vom 22. September 2008 bis zum 1. November 2008 gesendet hatte. Er machte geltend, aus diesen Nachrichten gehe hervor, dass weiterhin intime Beziehungen zwischen den Eheleuten bestünden, was die Behauptung, er berufe sich in rechtsmissbräuchlicher Weise auf die Ehe, "vollumfänglich" entkräfte. Das Verwaltungsgericht erkannte das neue Beweismittel zu den Akten, ermöglichte den Verfahrensbeteiligten die Einreichung von Schlussbemerkungen - was X._ mit Eingabe vom 23. März 2009 tat - und wies die Beschwerde mit Urteil vom 21. April 2009 ab. F. Mit Eingabe vom 26. Mai 2009 führt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, das Urteil des Verwaltungsgerichts des Kantons Bern vom 21. April 2009 aufzuheben und ihm - dem Beschwerdeführer - die Aufenthaltsbewilligung zu erneuern; eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Die Einwohnerdienste (Migration und Fremdenpolizei) der Stadt Bern beantragen, die Beschwerde abzuweisen. Denselben Antrag stellen die Polizei- und Militärdirektion des Kantons Bern, das Verwaltungsgericht des Kantons Bern und das Bundesamt für Migration. G. Mit Verfügung vom 2. Juni 2009 hat der Abteilungspräsident der Beschwerde - antragsgemäss - aufschiebende Wirkung zuerkannt.