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.

Erwägungen:
1. 1.1 <ref-law> schliesst die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen aus, auf deren Erteilung weder nach dem Bundes- noch dem Völkerrecht ein Rechtsanspruch besteht.
1.2 Gemäss Art. 126 Abs. 1 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20), welches am 1. Januar 2008 in Kraft getreten ist, bleibt für Gesuche, die vor diesem Zeitpunkt gestellt worden sind, das bisherige Recht anwendbar. Das muss auch gelten für Entscheide über die Verlängerung einer Aufenthaltsbewilligung, wenn sie - wie hier - noch unter der Herrschaft des bisherigen Rechts ergangen sind (vgl. Urteil 2C_657/2007 vom 26. Mai 2008, E. 1.2). Die vorliegende Streitsache ist daher noch nach dem inzwischen aufgehobenen Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) und seinen Ausführungserlassen zu beurteilen.
1.3 Da der Beschwerdeführer formell mit einer Schweizer Bürgerin verheiratet ist, hat er gestützt auf Art. 7 Abs. 1 ANAG einen grundsätzlichen Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist daher insoweit zulässig und der Beschwerdeführer hierzu legitimiert (<ref-law>). Mangels eines Anspruches nicht einzutreten ist hingegen auf die Beschwerde, soweit damit eine Aufenthaltsbewilligung gemäss Art. 4 ANAG ("nach freiem Ermessen") zum Gegenstand des Verfahrens gemacht werden soll (vgl. S. 16/17 der Beschwerdeschrift).
1.4 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG; vgl. <ref-ruling> E. 2.1 S. 245 f.), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254).
Eine qualifizierte Rügepflicht gilt u.a. hinsichtlich der Verletzung von Grundrechten. Das Bundesgericht prüft solche Rügen nur, wenn sie in der Beschwerde präzise vorgebracht und begründet worden sind (<ref-law>; vgl. <ref-ruling> E. 1.4.2 S. 254; <ref-ruling> E. 1.4 S. 287).
1.5 Das Bundesgericht legt sodann seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und <ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>; vgl. <ref-ruling> E. 1.5 S. 146 f.).
2. 2.1 Gemäss Art. 7 Abs. 2 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers keinen Anspruch auf Erteilung der ihm nach Absatz 1 grundsätzlich zustehenden Bewilligung, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern und namentlich jene über die Begrenzung der Zahl der Ausländer zu umgehen. Erfasst wird davon die sog. Scheinehe bzw. Ausländerrechtsehe, bei der die Ehegatten von vornherein keine echte eheliche Gemeinschaft beabsichtigen (<ref-ruling> E. 2.1 S. 151; <ref-ruling> E. 4a S. 55, mit Hinweisen). Auch wenn die Ehe nicht bloss zum Schein eingegangen worden ist, heisst dies nicht zwingend, dass dem ausländischen Ehepartner der Aufenthalt bzw. die Niederlassung ungeachtet der weiteren Entwicklung gestattet werden muss. Zu prüfen ist diesfalls, ob sich die Berufung auf die Ehe nicht anderweitig als rechtsmissbräuchlich erweist (BGE <ref-ruling> E. 5a S. 56, mit Hinweisen).
2.2 Rechtsmissbrauch im Zusammenhang mit Art. 7 ANAG liegt vor, wenn der Ausländer sich im Verfahren um Erteilung einer fremdenpolizeilichen Anwesenheitsbewilligung auf eine Ehe beruft, welche nur (noch) formell und ohne Aussicht auf Aufnahme bzw. Wiederaufnahme einer ehelichen Gemeinschaft besteht (<ref-ruling> E. 2.2 S. 151 mit Hinweisen). Ein Rechtsmissbrauch darf aber nicht leichthin angenommen werden, namentlich nicht schon deshalb, weil die Ehegatten nicht mehr zusammenleben oder ein Eheschutz- oder Scheidungsverfahren eingeleitet worden ist. Die gesetzliche Regelung will die Fortführung des Familienlebens in der Schweiz - allenfalls auch in einer vorübergehenden Krisensituation - ermöglichen und absichern, jedoch nicht einem missbräuchlichen, ausschliesslich ausländerrechtlich motivierten Festhalten an einer klar gescheiterten Ehe Vorschub leisten (BGE <ref-ruling> E. 5a mit Hinweisen). Zwar soll die Regelung verhindern, dass der ausländische Partner mit Blick auf die Erneuerung seiner Bewilligung der Willkür des schweizerischen Gatten ausgeliefert wird; damit akzeptierte der Gesetzgeber jedoch nicht, dass jener seinerseits Art. 7 ANAG zu institutsfremden Zwecken missbraucht (<ref-ruling> E. 4.1 u. 4.2). Ob dies der Fall ist, entzieht sich in der Regel einem direkten Beweis und muss deshalb aufgrund von Indizien erstellt werden (<ref-ruling> E. 10.2 S. 135; <ref-ruling> E. 5a S. 57). Dabei sind klare Hinweise dafür erforderlich, dass die Führung einer Lebensgemeinschaft tatsächlich nicht mehr beabsichtigt und realistischerweise nicht mehr zu erwarten ist (<ref-ruling> E. 2.2 S. 151; <ref-ruling> E. 5a S. 56 f. mit Hinweisen).
3. 3.1 Das Verwaltungsgericht stellte fest, vorliegend sei die Ehe - nach rund zweieinhalbjährigem Zusammenleben - faktisch bereits mehr als eineinhalb Jahre getrennt. Es erwog, die Vorinstanz habe die im Verfahren eingeholten Stellungnahmen der Eheleute zu den gestellten Fragen sorgfältig gewürdigt und habe ohne Rechtsverletzung darauf schliessen dürfen, dass die Führung einer Lebensgemeinschaft tatsächlich nicht mehr beabsichtigt und realistischerweise nicht mehr zu erwarten sei. Die Würdigung aller Umstände zwinge zum Schluss, dass sich der Beschwerdeführer auf eine auch für ihn seit geraumer Zeit erkennbar inhaltsleer gewordene Beziehung berufe, an deren Wiederaufleben er nicht mehr ernsthaft glauben könne.
3.2 Der Beschwerdeführer wirft dem Verwaltungsgericht - namentlich mit Bezug auf die Verneinung des Ehewillens seiner Frau - eine offensichtlich unrichtige und unvollständige Sachverhaltsfeststellung vor. Er macht geltend, die Aussagen und das Verhalten der Ehefrau seien widersprüchlich und gäben keinen Hinweis auf einen definitiven Willen, das Eheleben aufzugeben. So kontaktiere sie ihn regelmässig mit u.a. intimen SMS, lasse ihn zeitweise bei sich übernachten und wolle sich auch mit ihm versöhnen. Trotz dieser klar erkennbaren Widersprüche ("Katz- und Maus-Spiel") habe das Verwaltungsgericht auf weitere Abklärungen verzichtet, was zu unhaltbaren Sachverhaltsfeststellungen geführt habe. Im Umstand, dass das Verwaltungsgericht die Ehefrau nicht erneut förmlich befragt hat (namentlich zu den neu zu den Akten gegebenen Beweismitteln ["SMS]") erblickt der Beschwerdeführer ausserdem eine Verletzung seines Anspruchs auf rechtliches Gehör (<ref-law>); ebenso rügt er eine von den Vorinstanzen angenommene unzulässige Heilung der durch die erstverfügende Behörde begangenen Gehörsverletzung (S. 15 der Beschwerdeschrift).
3.2 Der Beschwerdeführer wirft dem Verwaltungsgericht - namentlich mit Bezug auf die Verneinung des Ehewillens seiner Frau - eine offensichtlich unrichtige und unvollständige Sachverhaltsfeststellung vor. Er macht geltend, die Aussagen und das Verhalten der Ehefrau seien widersprüchlich und gäben keinen Hinweis auf einen definitiven Willen, das Eheleben aufzugeben. So kontaktiere sie ihn regelmässig mit u.a. intimen SMS, lasse ihn zeitweise bei sich übernachten und wolle sich auch mit ihm versöhnen. Trotz dieser klar erkennbaren Widersprüche ("Katz- und Maus-Spiel") habe das Verwaltungsgericht auf weitere Abklärungen verzichtet, was zu unhaltbaren Sachverhaltsfeststellungen geführt habe. Im Umstand, dass das Verwaltungsgericht die Ehefrau nicht erneut förmlich befragt hat (namentlich zu den neu zu den Akten gegebenen Beweismitteln ["SMS]") erblickt der Beschwerdeführer ausserdem eine Verletzung seines Anspruchs auf rechtliches Gehör (<ref-law>); ebenso rügt er eine von den Vorinstanzen angenommene unzulässige Heilung der durch die erstverfügende Behörde begangenen Gehörsverletzung (S. 15 der Beschwerdeschrift).
3.3 3.3.1 Das rechtliche Gehör gemäss <ref-law> dient einerseits der Sachaufklärung, andererseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheides dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht des Betroffenen, sich vor Erlass eines solchen Entscheides zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen. Der Anspruch auf rechtliches Gehör umfasst als Mitwirkungsrecht somit alle Befugnisse, die einer Partei einzuräumen sind, damit sie in einem Verfahren ihren Standpunkt wirksam zur Geltung bringen kann (<ref-ruling> E. 3.2 S. 494; <ref-ruling> E. 2b S. 56; <ref-ruling> E. 4b S. 268, mit Hinweisen).
Nach der Rechtsprechung kann das Gericht das Beweisverfahren schliessen, wenn die Beweisanträge eine nicht erhebliche Tatsache betreffen oder offensichtlich untauglich sind oder wenn es aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 2.1 S. 428; <ref-ruling> E. 4a S. 211).
<ref-law> vermittelt auch nicht zwingend das Recht, mündlich angehört zu werden. Eine mündliche Äusserungsmöglichkeit kann aber geboten sein wegen persönlicher Umstände, die sich nur aufgrund einer mündlichen Anhörung klären lassen (vgl. Gerold Steinmann, in: Kommentar BV, 2. Auflage 2008, Rz. 25 zu <ref-law>) bzw. wenn sich eine solche Anhörung für den zu fällenden Entscheid als unerlässlich erweist (<ref-ruling> E. 4 S. 469 f.).
Eine nicht besonders schwer wiegende Verletzung des rechtlichen Gehörs kann geheilt werden, wenn die betroffene Person die Möglichkeit erhält, sich vor einer Beschwerdeinstanz zu äussern, die sowohl den Sachverhalt wie die Rechtslage mit mindestens gleicher Kognition wie die Vorinstanz prüfen kann (<ref-ruling> E. 5.1 S. 390; <ref-ruling> E. 6b/aa S. 123, Steinmann, a.a.O., Rz. 32 zu <ref-law>).
3.3.2 Im Umstand, dass die Vorbringen des Beschwerdeführers zur ehelichen Situation in der Verfügung der Einwohnerdienste der Stadt Bern vom 6. Dezember 2007 keinen direkten Niederschlag gefunden haben (vorne lit. C) liegt, wie das Verwaltungsgericht zutreffend annehmen durfte, keine schwerwiegende Verletzung des Anspruchs auf rechtliches Gehör, zumal die erste Beschwerdeinstanz - die kantonale Polizei- und Militärdirektion - noch einmal ein umfassendes Beweisverfahren zur ehelichen Situation durchgeführt hat und der Beschwerdeführer dazu mehrfach - auch in Form von Schlussbemerkungen - Stellung nehmen konnte. Nach diesen ergänzenden Beweiserhebungen hat die Direktion mit der gleichen Kognition über die Verlängerung der Aufenthaltsbewilligung entschieden wie die erstverfügenden Einwohnerdienste (vgl. E. 2.3.2 des angefochtenen Entscheides mit Hinweis auf Art. 66 des bernischen Verwaltungsrechtspflegegesetzes). Die Rüge, das Verwaltungsgericht habe in unzulässiger Weise eine Heilung der begangenen Gehörsverletzung angenommen, ist damit unbegründet.
3.3.3 Eine Gehörsverletzung liegt auch nicht darin, dass das Verwaltungsgericht die neu ins Verfahren eingebrachten SMS-Nachrichten der Ehefrau an den Ehemann (mit teilweise sexuellem Inhalt) nicht zum Anlass für eine persönliche Befragung von Y._ genommen hatte. Der Beschwerdeführer verzichtete darauf, einen entsprechenden Antrag zu stellen; das Verwaltungsgericht nahm die neuen Beweismittel ausserdem förmlich zu den Akten und es hat sich im angefochtenen Entscheid (E. 4.3) ausdrücklich damit auseinander gesetzt. Die Gehörsrüge ist auch unter diesem Gesichtswinkel unbegründet.
3.3.4 Schliesslich kann dem Verwaltungsgericht - angesichts der langen Trennung der Eheleute - nicht vorgeworfen werden, es habe den Sachverhalt geradezu offensichtlich unrichtig festgestellt. Zwar erscheinen die Aussagen und das Verhalten der Ehefrau nicht widerspruchsfrei, was auch anders gewertet werden könnte. Dem Verwaltungsgericht ist dies jedoch nicht entgangen und es hat im angefochtenen Entscheid darauf Bezug genommen. Auch erweist sich seine Feststellung, Y._ habe in mehreren SMS-Nachrichten unmissverständlich zum Ausdruck gebracht, dass sie vom Beschwerdeführer getrennt sei und sein Verhalten als aufdringlich empfinde, als richtig (vgl. etwa S. 5 der entsprechenden Belegliste).
3.4 Nach dem Gesagten ist das Verwaltungsgericht von der bundesgerichtlichen Rechtsprechung zum Rechtsmissbrauchsverbot von Art. 7 Abs. 2 ANAG ausgegangen und hat diese zutreffend angewendet. Aus den vorhandenen Indizien durfte das Verwaltungsgericht zulässigerweise schliessen, dass - trotz der noch vorhandenen, oft rein sexuell motivierten Kontakte unter den Eheleuten - vorliegend mit einer Wiederaufnahme einer (umfassenden) ehelichen Lebensgemeinschaft nicht mehr zu rechnen ist. Daran ändert der Einwand des Beschwerdeführers, dass aufgrund dieser Kontakte eine Wiederaufnahme des Zusammenlebens sehr wohl möglich erscheine, nichts. Wer sich auf einer solchen Grundlage darauf einrichtet, das in Art. 7 Abs. 1 ANAG vorgesehene Anwesenheitsrecht in Anspruch zu nehmen, handelt rechtsmissbräuchlich.
4. Die Beschwerde ist als unbegründet abzuweisen, soweit darauf eingetreten werden kann.
Bei diesem Verfahrensausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (Art. 65 und 66 BGG). Parteientschädigungen sind nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, der Einwohnergemeinde Bern (Einwohnerdienste [Migration und Fremdenpolizei]), der Polizei- und Militärdirektion und dem Verwaltungsgericht des Kantons Bern sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 30. November 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Klopfenstein