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.