Sachverhalt:
A. Der aus Mazedonien stammende X._ (geb. 1972) zeugte während der Ehe mit seiner Landsfrau Y._ drei Kinder. Am 13. April 2005 wurde diese Ehe geschieden. X._ erhielt das alleinige Sorgerecht über die drei Kinder zugesprochen. Wenige Tage später, am 26. April 2005, heiratete er die um 26 Jahre ältere Z._, welche das Schweizer Bürgerrecht besitzt. Am 21. August 2005 reiste er in die Schweiz ein, wo er im Rahmen des Familiennachzugs eine Aufenthaltsbewilligung erhielt. Diese wurde mehrfach verlängert, zuletzt bis zum 20. August 2008. Am 19. November 2005 hatte ihm seine frühere Ehefrau ein viertes Kind geboren. Alle Kinder leben in Mazedonien.
B. Nachdem die Stadtpolizei Winterthur im Auftrag (vom 18. März 2008) der Einwohnerkontrolle die Wohnsituation der Eheleute X._ und Z._ abgeklärt (Bericht vom 16. Juni 2008) und das Ehepaar im Auftrag des kantonalen Migrationsamtes zur Ehe befragt hatte, gewährte das Amt X._ zur beabsichtigten Nichtverlängerung der Aufenthaltsbewilligung das rechtliche Gehör und wies dessen gegenteiliges Gesuch mit Verfügung vom 9. September 2010 anschliessend ab. Zur Begründung führte das Amt im Wesentlichen aus, X._ und Z._ hätten nie die Absicht gehabt, eine wirkliche Ehe zu führen.
Der gegen diese Verfügung erhobene Rekurs bei der Sicherheitsdirektion des Kantons Zürich blieb erfolglos, und mit Urteil vom 15. Dezember 2011 wies das Verwaltungsgericht des Kantons Zürich die gegen den Direktionsentscheid vom 12. Oktober 2010 erhobene Beschwerde ebenfalls ab, soweit es darauf eintrat. Auf die von X._ verlangte Anhörung der Ehefrau bzw. deren Sohnes aus erster Ehe hatte es verzichtet, ebenso auf die geforderte Einholung eines Amtsberichts bei der Einwohnerkontrolle Winterthur zur Frage, unter welchen Umständen und aus welchen Gründen es zum Abklärungsauftrag vom 18. März 2008 an die Stadtpolizei Winterthur gekommen sei.
C. Mit Eingabe vom 19. Januar 2012 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit den Anträgen, das Urteil des Verwaltungsgerichts vom 15. Dezember 2011 aufzuheben und ihm - dem Beschwerdeführer - die Aufenthaltsbewilligung zu verlängern; sodann sei das Verfahren an die Vorinstanz zurückzuweisen und diese einzuladen, den verfahrensrechtlichen Anträgen (betreffend Befragung der Ehefrau bzw. des Sohnes und betreffend Einholen eines Amtsberichts) stattzugeben.
Die Sicherheitsdirektion des Kantons Zürich beantragt, die Beschwerde abzuweisen. Das Verwaltungsgericht verzichtet auf Vernehmlassung. Das Bundesamt für Migration schliesst auf Abweisung der Beschwerde.
X._ hat von der Möglichkeit, sich nochmals zu äussern, keinen Gebrauch gemacht.
Erwägungen:
1. 1.1 Gemäss Art. 83 lit. c Ziff. 2 BGG ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts unzulässig gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt.
1.2 Ausländische Ehegatten von Schweizerinnen und Schweizern haben Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen (Art. 42 Abs. 1 AuG). Vom Erfordernis des Zusammenwohnens wird abgesehen, wenn für getrennte Wohnungen wichtige Gründe geltend gemacht werden und die Familiengemeinschaft weiter besteht (Art. 49 AuG). Die Ansprüche nach Artikel 42 erlöschen u.a., wenn sie rechtsmissbräuchlich geltend gemacht werden, namentlich um Vorschriften dieses Gesetzes und seiner Ausführungsbestimmungen über die Zulassung und den Aufenthalt zu umgehen (Art. 51 Abs. 1 lit. a AuG).
Der Beschwerdeführer macht geltend, mit Z._, mit welcher er seit dem 26. April 2005 verheiratet ist und welche das Schweizer Bürgerrecht besitzt, zusammenzuwohnen. Er hat nach dem Gesagten einen grundsätzlichen Anspruch auf Erteilung einer Aufenthaltsbewilligung. Die Beschwerde ist zulässig (Art. 83 lit. c Ziff. 2 BGG e contrario) und der Beschwerdeführer hierzu legitimiert (Art. 89 Abs. 1 BGG). Für das Eintreten genügt, wenn die ausländische Person dartut, dass potenziell ein Anspruch auf die beantragte Bewilligung besteht; ob die jeweiligen Voraussetzungen erfüllt sind, bildet Gegenstand der materiellen Beurteilung (BGE 136 II 177 E. 1.1 S. 179 f., 497 E. 3.3 S. 500 f.).
1.3 Mit der Beschwerde kann eine Rechtsverletzung nach Art. 95 und 96 BGG geltend gemacht werden. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es legt seinem Urteil die Sachverhaltsfeststellungen der Vorinstanz zugrunde (Art. 105 Abs. 1 BGG). In Ergänzung zu den Rügen, die sich auf Art. 95 f. BGG stützen, sind unter den engen Voraussetzungen von Art. 97 Abs. 1 BGG zwar auch Vorbringen gegen die Sachverhaltsfeststellung zulässig. Ein solcher Einwand kann nach der letztgenannten Bestimmung aber nur erhoben werden, wenn die Feststellung des Sachverhalts durch die Vorinstanz offensichtlich unrichtig, d.h. willkürlich ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (BGE 133 II 249 E. 1.2.2 S. 252; 133 III 393 E. 7.1 S. 398). Zudem ist vom Beschwerdeführer aufzuzeigen, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG).
1.4 Im Bereich der Beweiswürdigung steht dem Sachgericht ein erheblicher Ermessensspielraum zu (BGE 120 Ia 31 E. 4b S. 40). Nach der Rechtsprechung kann es ausserdem 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. Das Bundesgericht greift nur ein, wenn die Beweiswürdigung offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, auf einem offensichtlichen Versehen beruht oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (BGE 130 II 425 E. 2.1 S. 428; 124 I 208 E. 4a S. 211).
2. Der Beschwerdeführer macht zunächst geltend, das Verwaltungsgericht habe falsches Recht angewendet, indem es die Bewilligungsverweigerung gestützt auf Art. 51 Abs. 2 lit. a AuG (Erlöschen der Ansprüche von Ehegatten Niedergelassener, Pflegekindern und bei Auflösung der Familiengemeinschaft) geschützt habe. Die Ehefrau des Beschwerdeführers sei aber Schweizerin.
Dieser Einwand trifft zwar zu, ist jedoch für das Ergebnis des angefochtenen Entscheides ohne Bedeutung: Sowohl Art. 51 Abs. 1 lit. a als auch Art. 51 Abs. 2 lit. a AuG umschreiben den Rechtsmissbrauch als Erlöschensgrund gleichartig. Die entsprechende Rüge des Beschwerdeführers stösst damit ins Leere.
3.1 Gemäss Art. 51 Abs. 1 lit. a AuG erlöschen die Ansprüche nach Art. 42 AuG, wenn sie rechtsmissbräuchlich geltend gemacht werden, namentlich um Vorschriften dieses Gesetzes und seiner Ausführungsbestimmungen über die Zulassung und den Aufenthalt zu umgehen. Erfasst wird davon die sogenannte Scheinehe bzw. Ausländerrechtsehe. Ein Bewilligungsanspruch entfällt demnach, wenn von vornherein nie der Wille bestand, eine dauerhafte Gemeinschaft zu begründen, und der einzige Zweck der Heirat darin liegt, dem Ausländer zu einer fremdenpolizeilichen Bewilligung zu verhelfen (vgl. Urteil 2C_125/2011 vom 31. August 2011 E. 3.1 sowie BGE 128 II 145 E. 2.1 S. 151 mit Hinweisen). Auch die vom AuG gewährleisteten Rechtsansprüche stehen unter dem Vorbehalt des Rechtsmissbrauchsverbotes, jedoch beschränkt sich dessen Anwendung - aufgrund der veränderten Anspruchsvoraussetzungen gegenüber dem früheren Recht - im Wesentlichen auf solche Fälle, in denen die Ehepartner nur zum Schein zusammenwohnen. Fehlt es dagegen an einem Zusammenwohnen, so scheitert der Bewilligungsanspruch bereits an den gesetzlichen Voraussetzungen und die Frage des Rechtsmissbrauchs erübrigt sich (BGE 136 II 113 E. 3.2 S. 116).
Das Vorliegen einer Ausländerrechtsehe darf nicht leichthin angenommen werden (vgl. BGE 128 II 145 E. 2.2 S. 151). Es ist Sache der Migrationsbehörden, eine Scheinehe nachzuweisen. Dabei müssen die Behörden den Sachverhalt grundsätzlich von Amtes wegen untersuchen. Der Untersuchungsgrundsatz wird aber durch die Mitwirkungspflicht der Betroffenen relativiert: So sind Ausländerinnen und Ausländer sowie an Verfahren nach dem AuG beteiligte Dritte verpflichtet, an der Feststellung des für die Anwendung des Gesetzes massgebenden Sachverhalts mitzuwirken; sie müssen u.a. insbesondere zutreffende und vollständige Angaben über die für die Regelung des Aufenthalts wesentlichen Tatsachen machen (vgl. Art. 90 lit. a AuG sowie Urteil 2C_125/2011 vom 31. August 2011 E. 3.2).
3.2 Ob eine Scheinehe geschlossen wurde, entzieht sich oft einem direkten Beweis und ist bloss durch Indizien zu erstellen. Feststellungen des kantonalen Richters über das Bestehen von solchen Hinweisen können äussere Gegebenheiten, aber auch innere psychische Vorgänge betreffen (Wille der Ehegatten). In beiden Fällen handelt es sich um tatsächliche Feststellungen, welche für das Bundesgericht grundsätzlich verbindlich sind (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 1 und 2 BGG; BGE 133 II 249 E. 1.4.3 S. 254 f.). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe sei rechtsmissbräuchlich oder bezwecke die Umgehung fremdenpolizeilicher Vorschriften (BGE 128 II 145 E. 2.3 S. 152 mit Hinweisen).
Für die Annahme einer Scheinehe bedarf es konkreter Hinweise darauf, dass die Ehegatten nicht eine eigentliche Lebensgemeinschaft führen wollen, sondern die Ehe nur aus fremdenpolizeilichen Überlegungen geschlossen haben. Diesbezügliche Indizien lassen sich unter anderem darin erblicken, dass dem Ausländer die Wegweisung drohte, etwa weil er ohne Heirat keine Aufenthaltsbewilligung erhalten hätte oder sie ihm nicht verlängert worden wäre. Für das Vorliegen einer Ausländerrechtsehe können sodann die Umstände und die kurze Dauer der Bekanntschaft sprechen sowie insbesondere die Tatsache, dass die Ehegatten - die nach geltendem Recht für das Entstehen des Anspruchs nach Art. 42 AuG grundsätzlich zusammenwohnen müssen (vorne E. 1.2 und E. 3.1 sowie BGE 136 II 113) - eine Wohngemeinschaft gar nie aufgenommen haben. Dasselbe gilt, wenn für die Heirat eine Bezahlung vereinbart wurde oder wenn ein erheblicher Altersunterschied zwischen den Ehepartnern besteht. Dass die Begründung einer wirklichen Lebensgemeinschaft gewollt war, kann umgekehrt nicht schon daraus abgeleitet werden, dass die Ehegatten während einer gewissen Zeit zusammenlebten und intime Beziehungen unterhielten; ein derartiges Verhalten kann auch nur vorgespielt sein, um die Behörden zu täuschen (BGE 122 II 289 E. 2b S. 295 mit Hinweisen). Eine Scheinehe liegt demgegenüber nicht bereits dann vor, wenn ausländerrechtliche Motive für den Eheschluss mitentscheidend waren. Erforderlich ist zusätzlich, dass der Wille zur Führung einer Lebensgemeinschaft - zumindest bei einem der Ehepartner - von Anfang an nicht gegeben ist (vgl. BGE 121 II 97 E. 3b S. 101 f. mit Hinweisen).
3.3 Der Beschwerdeführer liess sich wenige Tage vor der Heirat mit der um 26 Jahre älteren Z._ von seiner damaligen mazedonischen Ehefrau scheiden, wobei ihm das Sorgerecht über seine Kinder übertragen wurde (vorne lit. A). Ohne die Eheschliessung mit einer Schweizer Bürgerin hätte er kein Aufenthaltsrecht in der Schweiz erhalten. Nach den für das Bundesgericht grundsätzlich verbindlichen Sachverhaltsfeststellungen des Verwaltungsgerichts, welche durch die Akten gestützt werden, war aus Sicht der neuen Ehefrau ursprünglich geplant, die Kinder in die Schweiz zu holen ("sie sind so krank und so mager"). Das Verwaltungsgericht stellte weiter fest, es fehle den Eheleuten an gemeinsamen Erinnerungen an das erstmalige Treffen und an rituelle Feiern, an die Umstände des Eheschlusses und an gemeinsamen Interessen oder Hobbys. Auch führten die Eheleute getrennte Kassen. Die Ehefrau halte sich aus gesundheitlichen Gründen häufig und während längerer Zeit in Serbien auf; sie könne nur spärliche Angaben zur Ausbildung und zum Beruf ihres Ehemannes machen, kenne dessen Arbeitgeber nicht und vermöge auch sonst kaum die Namen seiner Brüder und Kinder zu nennen. Umgekehrt habe auch der Ehemann nur beschränkte Kenntnisse von den vorehelichen Kindern seiner Ehefrau. Daraus schloss das Verwaltungsgericht, die Umstände in ihrer Gesamtheit liessen einzig den Schluss zu, dass die Eheleute nie die Absicht gehabt hätten, eine auf Dauer angelegte wirkliche Ehe miteinander zu führen. Der Beschwerdeführer habe anlässlich der Gesuche um Verlängerung der Aufenthaltsbewilligung die Behörden vielmehr getäuscht, indem er seinen Anspruch rechtsmissbräuchlich auf eine nur formell bestehende Ehe gestützt habe.
3.4 Der Beschwerdeführer hält diese Sachverhaltsfeststellung und Beweiswürdigung für willkürlich. Ausserdem bemängelt er eine Gehörsverweigerung (vgl. Art. 29 Abs. 2 BV) durch die Nichtabnahme von beantragten Beweismitteln durch das Verwaltungsgericht. Namentlich rügt er, es hätte eine Befragung der Ehefrau und ihres Sohnes A._ durch das Verwaltungsgericht selber stattfinden müssen. Auch betont er die Wichtigkeit des vom Gericht verweigerten Amtsberichts über die Hintergründe des Abklärungsauftrags an die Stadtpolizei Winterthur (vorne lit. B) und spricht von "Verdacht auf Denunziation und anonyme(r) falscher Anschuldigung".
3.5 Diese Einwände sind nicht geeignet, die vom Verwaltungsgericht getroffenen Sachverhaltsfeststellungen als unrichtig bzw. unvollständig und die von ihm daraus gezogenen rechtlichen Schlussfolgerungen als bundesrechtswidrig erscheinen zu lassen. Ebenso wenig liegt eine willkürliche Beweiswürdigung vor. Das Verwaltungsgericht hat sich mit den Beweisanträgen auseinander gesetzt: Im Falle der verlangten Befragung von Ehefrau und Sohn durfte es angesichts der Indizienlage willkürfrei davon ausgehen, die Beteiligten würden sich vorher absprechen, womit das Beweisergebnis von vornherein feststehe. Für diese Einschätzung durfte sich das Verwaltungsgericht auf die früher gemachten Aussagen der Ehefrau stützen, wonach diese inzwischen die Trennung eingeleitet habe ("Nein, nicht die Scheidung, die Trennung. Ich will nicht, dass X._ aus der Schweiz geworfen wird. Auf keinen Fall. (...). Das hätte er nicht verdient. Er ist ein sehr anständiger Mensch und arbeitet jeden Tag."). Was den vom Verwaltungsgericht verweigerten Amtsbericht über die Umstände des Abklärungsauftrages der Einwohnerkontrolle an die Stadtpolizei Winterthur betrifft, ist nicht ersichtlich, wie ein solcher auf die vom Gericht getroffenen Sachverhaltsfeststellungen einen Einfluss haben könnte. Der Beschwerdeführer tut jedenfalls nicht dar, inwiefern die Behebung eines diesbezüglichen allfälligen Mangels für den Ausgang des Verfahrens entscheidend sein könnte (vorne E. 1.3): Die Behörden handelten im Rahmen ihres gesetzlichen Auftrages, und die Beteiligten unterlagen der Mitwirkungspflicht (vorne E. 3.1). Zu dem im korrekten Verfahren erhobenen Beweisergebnis konnte der Beschwerdeführer ausserdem vor dem Erlass der Verfügung betreffend Nichtverlängerung der Aufenthaltsbewilligung Stellung nehmen (vgl. vorne lit. B).
3.6 Nach dem Gesagten erscheint es nicht bundesrechtswidrig, wenn das Verwaltungsgericht vorliegend aufgrund der Gesamtumstände auf eine Ausländerrechtsehe geschlossen und den Aufenthaltsanspruch des Beschwerdeführers als erloschen betrachtet hat. Mit Blick darauf verletzt die vom Migrationsamt verfügte und von den kantonalen Rechtsmittelinstanzen geschützte Nichtverlängerung der Aufenthaltsbewilligung auch die Garantie auf Schutz des Familienlebens (Art. 8 EMRK, Art. 13 Abs. 1 BV) nicht. Die Beschwerde erweist sich als unbegründet und ist abzuweisen.
4. Diesem Ausgang entsprechend hat der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen (Art. 65/66 BGG). Parteientschädigungen sind nicht geschuldet (Art. 68 Abs. 3 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Migrationsamt, der Sicherheitsdirektion und dem Verwaltungsgericht (4. Kammer) des Kantons Zürich sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 1. Oktober 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Klopfenstein