Sachverhalt:
A. Der aus Serbien stammende X._, geb. 14. Juli 1974, heiratete im August 1996 die in der Schweiz aufenthaltsberechtigte Landsmännin Z._, geb. 1972. Im April 1997 wurde ihm die Aufenthaltsbewilligung zum Verbleib bei der Ehefrau erteilt. Der Ehe entsprossen die Kinder A._, geb. 1998, und B._, geb. 2001, welche in die der Ehefrau 1999 erteilte Niederlassungsbewilligung einbezogen wurden. Die in den Jahren 2003 und 2004 anhängig gemachten Gesuche von X._ um Erteilung der Niederlassungsbewilligung wurden mangels Erfüllung der zeitlichen Voraussetzungen (2003) bzw. wegen Abwartens des Ausgangs eines gegen ihn angehobenen Strafverfahrens (2004) nicht an die Hand genommen. Am 25. Juni 2005 trennten sich die Eheleute X Z._, wobei die Kinder in der Obhut der Mutter blieben und weiterhin Kontakt zu ihrem Vater pflegten.
Mit Urteil des Obergerichts des Kantons Zürich vom 3. April 2007 wurde X._ der Widerhandlung gegen das Betäubungsmittelgesetz für schuldig befunden und zu einer Freiheitsstrafe von 18 Monaten verurteilt, bedingt vollziehbar bei einer Probezeit von zwei Jahren. Eine dagegen erhobene Beschwerde ans Bundesgericht blieb erfolglos (Urteil 6B_297/2007 vom 4. September 2007). Mit Verfügung vom 7. November 2007 wies die Sicherheitsdirektion des Kantons Zürich, Migrationsamt, das Gesuch von X._ um Verlängerung der Aufenthaltsbewilligung ab und setzte ihm Frist zum Verlassen des zürcherischen Kantonsgebiets. Dagegen rekurrierte X._ an den Regierungsrat des Kantons Zürich.
B. Die serbische Staatsangehörige Y._, geb. 4. Mai 1980, erhielt am 10. Januar 2002 eine Aufenthaltsbewilligung zum Verbleib bei ihrem im Kanton Zürich niedergelassenen Ehemann. Im Mai 2004 wurde die eheliche Gemeinschaft aufgegeben, worauf das Migrationsamt ihr Gesuch um Verlängerung der Aufenthaltsbewilligung abwies und sie wegwies. Dagegen wehrte sich Y._ erfolglos mit Rekurs und Wiedererwägung. Wegen einer bestehenden Schwangerschaft verzichteten die Zürcher Behörden jedoch einstweilen auf Vollziehungsvorkehren. Am 20. Januar 2007 kam der Sohn C._ zur Welt, welchen X._, der spätestens seit dem 1. Dezember 2006 mit Y._ zusammenwohnte, am 13. Juni 2007 als sein Kind anerkannte. Zudem wurde bekannt, dass Y._ seit dem 13. Dezember 2004 geschieden war. Am 21. Juni 2007 liess Y._ die Erteilung einer Aufenthaltsbewilligung bzw. Wiedererwägung beantragen und begründete dies insbesondere mit der neuen familiären Situation. Mit Schreiben vom 25. Juni 2007 teilte das Migrationsamt Y._ mit, sie habe die Schweiz unverzüglich zu verlassen, woran der geltend gemachte Sachverhalt nichts zu ändern vermöge. Auf ein abermaliges Wiedererwägungsgesuch hin bekräftigte das Migrationsamt diesen Standpunkt mit Schreiben vom 2. August 2007. Gegen das Schreiben des Migrationsamtes vom 25. Juni 2007 erhob Y._ Rekurs. Am 6. April 2008 hat Y._ die Tochter D._ geboren.
C. Mit Beschluss vom 3. September 2008 vereinigte der Regierungsrat des Kantons Zürich die Rekursverfahren von X._ und Y._ und wies die Rechtsmittel in der Hauptsache ab.
Mit Verfügung vom 13. Oktober 2008 dehnte das Bundesamt für Migration die Wegweisung von X._ auf das Gebiet der ganzen Schweiz aus.
D. Mit Entscheid vom 4. Februar 2009 wies das Verwaltungsgericht des Kantons Zürich, 4. Kammer, die von X._ und Y._ hiegegen eingereichte Beschwerde ab, soweit es darauf eintrat.
E. Mit gemeinsamer Eingabe vom 11. März 2009 erheben X._ und Y._ beim Bundesgericht Beschwerde mit den Anträgen, den Entscheid des Verwaltungsgerichts vom 4. Februar 2009 aufzuheben und das Migrationsamt des Kantons Zürich anzuweisen, X._ die Aufenthaltsbewilligung zu verlängern bzw. Y._ und den Kindern C._ und D._ eine Aufenthaltsbewilligung zu erteilen. Sodann ersuchen sie für das bundesgerichtliche Verfahren um unentgeltliche Prozessführung und Verbeiständung.
Die Staatskanzlei (im Auftrag des Regierungsrates) des Kantons Zürich und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich verzichtet auf Vernehmlassung.
F. Dem von den Beschwerdeführern gestellten Gesuch um aufschiebende Wirkung wurde mit Verfügung des Präsidenten der II. öffentlich-rechtlichen Abteilung vom 13. März 2009 entsprochen.

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. Gemäss Art. 4 des früheren Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG), welches vorliegend noch Anwendung findet (vgl. Art. 126 Abs. 1 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer [AuG; SR 142.20]), entscheidet die zuständige Behörde, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt und Niederlassung. Es besteht damit grundsätzlich kein Rechtsanspruch auf Erteilung oder Verlängerung einer Aufenthaltsbewilligung, es sei denn der Ausländer oder seine in der Schweiz lebenden Angehörigen könnten sich auf eine Sondernorm des Bundesrechts (einschliesslich Bundesverfassungsrecht) oder eines Staatsvertrages berufen (<ref-ruling> E. 1.1 S. 3 f. mit Hinweisen).
Da die Beschwerdeführerin 2 keine Rechtsansprüche mehr aus ihrer geschiedenen Ehe mit einem niedergelassenen Ausländer abzuleiten vermag und sich ein Anwesenheitsrecht für sie und ihre Kinder einzig aufgrund ihrer Beziehung zum Beschwerdeführer 1 ergeben kann, ist dessen ausländerrechtlicher Status vorweg zu klären.
1.2 Der Beschwerdeführer 1 lebt von seiner in der Schweiz niedergelassenen Ehefrau getrennt; fehlt es mithin am Erfordernis des Zusammenwohnens, entfällt der Anspruch auf Verlängerung der Aufenthaltsbewilligung gestützt auf Art. 17 Abs. 2 ANAG (vgl. <ref-ruling> E. 4 S. 116 ff. mit Hinweisen). Hingegen wurden seine beiden unter der Obhut der Mutter stehenden minderjährigen Kinder aus dieser Ehe in deren Niederlassungsbewilligung einbezogen, womit sie ein gefestigtes Anwesenheitsrecht in der Schweiz besitzen. Da die Beziehung zu diesen nach den Feststellungen des Verwaltungsgerichts intakt scheint und offenbar im Rahmen des Möglichen gelebt wird, hat der Beschwerdeführer 1 gestützt auf das in Art. 8 EMRK bzw. <ref-law> garantierte Recht auf Achtung des Familienlebens einen (bedingten) Rechtsanspruch auf die anbegehrte Aufenthaltsbewilligung (vgl. <ref-ruling> E. 1d und e S. 64 ff.).
1.3 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.4 Das Bundesgericht legt 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>).
2. 2.1 Hat ein Ausländer nahe Verwandte mit einem gefestigten Anwesenheitsrecht in der Schweiz und wird die intakte familiäre Beziehung tatsächlich gelebt, kann es Art. 8 EMRK bzw. <ref-law> verletzen, wenn ihm die Anwesenheit in der Schweiz untersagt und damit sein Familienleben vereitelt wird (<ref-ruling> E. 3.1 S. 285 mit Hinweisen). Der betreffende Anspruch gilt indessen nicht absolut. Vielmehr ist nach Art. 8 Ziff. 2 EMRK ein Eingriff in das durch Ziff. 1 geschützte Rechtsgut statthaft, soweit er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale Sicherheit, die öffentliche Ruhe und Ordnung, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung und zur Verhinderung von strafbaren Handlungen, zum Schutz der Gesellschaft und Moral sowie der Rechte und Freiheiten anderer notwendig ist. Die Konvention verlangt insofern eine Abwägung der sich gegenüberstehenden privaten Interessen an der Bewilligungserteilung und den öffentlichen Interessen an deren Verweigerung, wobei Letztere in dem Sinne überwiegen müssen, dass sich der Eingriff als notwendig erweist (<ref-ruling> E. 2 S. 6 mit Hinweisen).
2.2 Bei der im Hinblick auf die Bewilligungserteilung nach Art. 8 EMRK erforderlichen Interessenabwägung fällt das Interesse des um Bewilligung ersuchenden Ausländers namentlich dann ins Gewicht, wenn er mit der in der Schweiz anwesenheitsberechtigten Person zusammenlebt. Was das Verhältnis von Eltern zu ihren Kindern betrifft, gilt dies im Falle getrennt lebender Eltern für denjenigen Elternteil, dem das Sorgerecht zusteht. Der nicht sorgeberechtigte Ausländer kann die familiäre Beziehung zu seinen Kindern indessen zum Vornherein nur in einem beschränkten Rahmen, nämlich durch Ausübung des ihm eingeräumten Besuchsrechts, leben. Hierzu ist nicht unabdingbar, dass er dauernd im gleichen Land wie das Kind lebt und dort über eine Aufenthaltsbewilligung verfügt. Ein solches Besuchsrecht gegenüber einem in der Schweiz fest anwesenheitsberechtigten Kind verschafft dem ausländischen Elternteil daher im Allgemeinen noch keinen Anspruch auf dauernde Anwesenheit; den Anforderungen von Art. 8 EMRK ist Genüge getan, wenn das Besuchsrecht im Rahmen von Kurzaufenthalten vom Ausland her ausgeübt werden kann, wobei allenfalls dessen Modalitäten entsprechend auszugestalten sind. Ein weiter gehender Anspruch kann bestehen, wenn in wirtschaftlicher und affektiver Hinsicht eine besonders enge Beziehung zu den Kindern besteht, diese Beziehung wegen der Distanz zum Heimatland des Ausländers praktisch nicht aufrecht erhalten werden könnte und das bisherige Verhalten des Ausländers in der Schweiz zu keinerlei Klagen Anlass gegeben hat ("tadelloses Verhalten", "comportement irréprochable", "comportimento irreprensibile"; vgl. <ref-ruling> E. 3c S. 5, 22 E. 4a/b S. 25 f.; Urteile 2C_870/2008 vom 26. Mai 2009 E. 2.2; 2C_272/2008 vom 15. Januar 2009 E. 2.2; 2A.54/2007 vom 24. April 2007 E. 2.2; 2A.473/2006 vom 24. Januar 2007 E. 3.1; 2A.550/2006 vom 7. November 2006 E. 3.1; 2A.77/2006 vom 15. Februar 2006 E. 2.2.1; 2A.423/2005 vom 25. Oktober 2005 E. 4.3 mit weiteren Hinweisen). Wesentlich ist, ob gegen den Ausländer fremdenpolizeiliche Entfernungs- und Fernhaltegründe sprechen, insbesondere ob und inwieweit er sich massgebliches, strafrechtlich oder fremdenpolizeilich verpöntes Fehlverhalten hat zuschulden kommen lassen. Was das Erfordernis der besonderen gefühlsmässigen Intensität der Beziehung betrifft, ist dieses regelmässig dann als erfüllt zu erachten, wenn ein grosszügig ausgestaltetes Besuchsrecht eingeräumt ist und dieses kontinuierlich, spontan und reibungslos ausgeübt wird (Urteile 2D_30/2007 vom 17. Juli 2007 E. 4.2; 2A.550/2006 vom 7. November 2006 E. 3.1, sowie 2A.77/2006 vom 15. Februar 2006 E. 2.2.1, je mit Hinweisen).
2.3 Das Verwaltungsgericht hat die erwähnten Regeln, nach denen für die erleichterte Ausübung des Besuchsrechtes gegenüber einem hier anwesenheitsberechtigten Kind ausnahmsweise eine Aufenthaltsbewilligung beansprucht werden kann, zutreffend angewendet. Was die Beschwerdeführer dagegen vorbringen, vermag zu keinem anderen Ergebnis zu führen. Unstreitig ist, dass der Beschwerdeführer 1 in affektiver Hinsicht eine enge Beziehung zu seinen ehelichen, unter der Obhut der Mutter stehenden Kindern unterhält: Nach den Feststellungen der Vorinstanz halten sich die Kinder regelmässig jedes zweite Wochenende bei ihm auf und übernachten auch dort; ausserdem pflege er telefonischen Kontakt mit ihnen, interessiere sich für deren schulische Leistungen und nehme auch an Elternabenden teil. Zudem bemüht sich der Beschwerdeführer 1 offenbar darum, zumindest teilweise für den Unterhalt der ehelichen Kinder aufzukommen, doch habe die Kindsmutter zusätzlich vom Sozialamt unterstützt werden müssen, was naheliegend erscheint, wenn er - wie sich auch aus den Berechnungen im Gesuch um unentgeltliche Prozessführung ergibt - nur knapp in der Lage ist, zusammen mit den Einkünften seiner jetzigen Partnerin (Beschwerdeführerin 2) den Grundbedarf für die aus dieser Beziehung stammenden Kinder zu decken. Eine besonders enge Beziehung in wirtschaftlicher Hinsicht liegt demzufolge nicht vor.
Entscheidend ins Gewicht fällt jedoch vorliegend, dass die Voraussetzung eines klaglosen bisherigen Verhaltens des Beschwerdeführers 1 klarerweise nicht erfüllt ist. Dies ergibt sich allein schon aus der Tatsache, dass der Beschwerdeführer 1 wegen strafrechtlicher Verfehlungen zu einer Freiheitsstrafe von 18 Monaten verurteilt worden ist. Hinzu kommt, dass die Verurteilung wegen Widerhandlung gegen das Betäubungsmittelgesetz erfolgte, wobei es um den Transport grosser Mengen an harten Drogen (fast 15 kg Heroingemisch) und damit einen schweren Fall (kein Vergehen, sondern ein Verbrechen) ging. Das Bundesgericht verfolgt im Zusammenhang mit derartigen Straftaten - in Übereinstimmung mit der in Europa herrschenden Rechtsüberzeugung (vgl. <ref-ruling> E. 6 u. E. 7 S. 220 ff.) - fremdenpolizeilich eine strenge Praxis (<ref-ruling> E. 4a/aa S. 527). Abgesehen davon ist das Verhalten des Beschwerdeführers 1 auch insofern zu beanstanden, als er offenbar hohe Schulden hat (nach unwidersprochener Feststellung im angefochtenen Entscheid rund Fr. 100'000.--). Von einem "tadellosen Verhalten" im Sinne der Rechtsprechung kann somit nicht die Rede sein.
Zu Unrecht berufen sich die Beschwerdeführer überdies auf die sog. "Zweijahresregel" (Reneja-Praxis), wonach die Grenze, von der an einem Ausländer, der erstmals um eine Bewilligung ersucht oder nach bloss kurzer, ordnungsgemässer Aufenthaltsdauer die Erneuerung beantragt, in der Regel selbst dann keine Bewilligung mehr erteilt wird, wenn dem Ehepartner die Ausreise un- oder nur schwer zumutbar ist, bei einer Freiheitsstrafe von zwei Jahren liegt (<ref-ruling> E. 4.1 S. 185 mit Hinweisen). Zum einen ist diese (unter der Herrschaft des früheren allgemeinen Teils des Strafgesetzbuches entwickelte) Regel zugeschnitten auf den Fall eines mit einer Schweizerin verheirateten Ausländers; zum anderen handelt es sich dabei um einen blossen Richtwert, welcher nach Massgabe einer Interessenabwägung im Einzelfall auch über- oder unterschritten werden kann. Die Regel steht aber so oder so unter der Prämisse, dass die betroffenen Ehepartner in tatsächlich ungetrennter Ehe leben, was vorliegend nicht der Fall ist, weshalb sich die Frage der Zumutbarkeit der Ausreise für den anderen Ehegatten (bzw. die unter dessen Obhut stehenden Kinder) ohnehin nicht stellt und - wie erwähnt (oben E. 2.2) - strengere Voraussetzungen zum Tragen kommen.
2.4 Nach dem Gesagten sind die Voraussetzungen, unter denen einem Ausländer zur Ausübung des Besuchsrechts gegenüber in der Schweiz anwesenheitsberechtigten Kindern der dauernde Aufenthalt bewilligt werden muss, nicht erfüllt. Zwar erschwert sich dadurch die Ausübung des Besuchsrechts vom Heimatland Serbien aus angesichts der dem Beschwerdeführer 1 zur Verfügung stehenden Mittel, doch liegen diesbezüglich keine unüberwindbare Hindernisse vor. Für den Beschwerdeführer 1 selber, welcher erst im Alter von 23 Jahren in die Schweiz einreiste und hier seit 1997 lebt, erscheint eine Rückkehr ohne weiteres zumutbar, zumal er wieder mit einer Landsmännin liiert und insofern sprachlich und kulturell nach wie vor mit den Gepflogenheiten des Herkunftsstaates vertraut ist.
Die Verweigerung der für den Beschwerdeführer 1 anbegehrten Aufenthaltsbewilligung erweist sich nach dem Gesagten als verfassungs- und konventionskonform. Die Beschwerde ist insofern als unbegründet abzuweisen.
3. Besitzt der Beschwerdeführer 1 mithin kein gefestigtes Anwesenheitsrecht in der Schweiz, so lässt sich aus dem Recht auf Achtung des Familienlebens gemäss Art. 8 EMRK (bzw. <ref-law>) auch kein Rechtsanspruch auf die für die Beschwerdeführerin 2 und die beiden gemeinsamen Kinder anbegehrten Aufenthaltsbewilligungen ableiten. Ein Eingriff in das erwähnte Grundrecht steht überhaupt erst zur Diskussion, wenn einem Ausländer durch fremdenpolizeiliche Massnahmen verunmöglicht wird, in einem Staat zu bleiben, in welchem Mitglieder seiner Familie leben; andernfalls wird die Einheit und das faktische Zusammenleben der Familie nicht beeinträchtigt (<ref-ruling> E. 2b/cc S. 383 mit Hinweisen). Genau so verhält es sich vorliegend: Wird der Beschwerdeführerin 2 und deren Kindern der (weitere) Aufenthalt in der Schweiz verwehrt, hat dies, nachdem auch der Beschwerdeführer 1 das Land zu verlassen hat, keine Trennung dieser Familie zur Folge. Die Beschwerdeführer werden ihr Familienleben vielmehr im gemeinsamen Heimatstaat führen können.
Auf die Beschwerde ist demzufolge, soweit sie sich auf die Beschwerdeführerin 2 und die gemeinsamen Kinder bezieht, nicht einzutreten.
4. Die Beschwerdeführer haben für das bundesgerichtliche Verfahren um unentgeltliche Rechtspflege und Verbeiständung ersucht. Aufgrund der dargestellten, schon im angefochtenen Urteil zutreffend wiedergegebenen Sach- und Rechtslage besass das vorliegende Rechtsmittel keine ernsthaften Erfolgsaussichten; das Gesuch ist demzufolge abzuweisen (<ref-law>).
Entsprechend dem Ausgang sind die Kosten des bundesgerichtlichen Verfahrens den Beschwerdeführern unter solidarischer Haftung aufzuerlegen (Art. 66 Abs. 1 und 5 BGG), wobei ihrer finanziellen Lage bei der Bemessung der Gerichtsgebühr Rechnung zu tragen ist (vgl. <ref-law>). Auf die Zusprechung einer Parteientschädigung besteht kein Anspruch (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'000.-- werden den Beschwerdeführern auferlegt, unter solidarischer Haftung.
4. Dieses Urteil wird den Beschwerdeführern, der Sicherheitsdirektion, dem Regierungsrat (Staatskanzlei) und dem Verwaltungsgericht (4. Kammer) des Kantons Zürich sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 3. August 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Moser