Sachverhalt: A. X._, geb. 1972, reiste am 9. Juni 1999 zusammen mit A._, geb. 1976, mit dem sie seit 1998 nach Brauch verheiratet war, und der gemeinsamen Tochter Y._, geb. im Februar 1999, in die Schweiz ein. Die drei Familienangehörigen stammen aus dem Kosovo und gehören der ethnischen Minderheit der Roma (und davon der Untergruppe der so genannten Kosovo-Ägypter) an. Am 2. Mai 2002 lehnte das Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) das Asylgesuch von X._ und Y._ ab und wies die beiden aus der Schweiz weg. Dieser Entscheid wurde rechtskräftig. B. Am 17. September 2002 heiratete X._ in H._ den Schweizer Bürger B._, geb. 1962, und wohnte zunächst mit diesem zusammen im Kanton St. Gallen, wo ein Gesuch um Aufenthaltsbewilligung an X._ und deren Tochter Y._ eingereicht wurde. Im März 2003 kam das Kind Z._ zur Welt. Ein im Rahmen eines Verfahrens auf Anfechtung der Vaterschaft eingeholtes DNA-Gutachten ergab, dass B._ mit an Sicherheit grenzender Wahrscheinlichkeit der Vater von Z._ ist. Die Ehe B._ - X._ wurde später geschieden und Z._ unter die alleinige elterliche Sorge der Mutter gestellt. Spätestens anfangs 2003 zog X._ mit ihren beiden Töchtern zu ihrem Bruder nach K._ im Kanton Zürich. Dort stellte sie am 28. August 2003 ebenfalls ein Gesuch um Erteilung der Aufenthaltsbewilligung, auf das aber nicht eingetreten wurde. C. Mit Verfügung vom 8. Juli 2003 lehnte das Ausländeramt des Kantons St. Gallen das Gesuch um Erteilung von Aufenthaltsbewilligungen an X._ und Y._ ab. Beschwerden beim Justiz- und Polizeidepartement sowie beim Verwaltungsgericht des Kantons St. Gallen blieben erfolglos. Mit Urteil 2A.514/2005 vom 31. Januar 2006 hiess das Bundesgericht eine gegen den Entscheid des Verwaltungsgerichts des Kantons St. Gallen vom 20. Juni 2005 erhobene Verwaltungsgerichtsbeschwerde gut, soweit es darauf eintrat, hob das verwaltungsgerichtliche Urteil auf und wies die Sache an das Verwaltungsgericht des Kantons St. Gallen zurück zu ergänzender Sachverhaltsfeststellung und zu neuem Entscheid im Sinne der Erwägungen. Dabei erwog das Bundesgericht im Wesentlichen, die Frage der Zumutbarkeit der Ausreise für Angehörige der Minderheit der Kosovo-Ägypter setze situationsspezifische Abklärungen voraus, welche bisher fehlten. In der Folge nahm das Verwaltungsgericht ergänzende Abklärungen vor. Am 19. Oktober 2006 wies es die Beschwerde (wiederum) ab. Mit Urteil 2A.688/2006 vom 29. Juni 2007 wies das Bundesgericht eine dagegen erhobene Beschwerde ab. D. Am 4. Juli 2007 stellten X._ und Y._ ein weiteres Gesuch um Erteilung der Aufenthaltsbewilligung im Kanton Zürich. Mit Verfügung vom 17. September 2007 lehnte das Migrationsamt des Kantons Zürich das Gesuch ab, da sich keine wesentliche Veränderung der Umstände ergeben habe. Am 9. Januar 2008 wies der Regierungsrat des Kantons Zürich einen dagegen erhobenen Rekurs ab. Mit Entscheid vom 20. August 2008 wies das Verwaltungsgericht des Kantons Zürich, 4. Kammer, eine dagegen eingereichte Beschwerde ab, soweit es darauf eintrat. E. X._ und Y._ führen gegen das Urteil des Verwaltungsgerichts des Kantons Zürich beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, den Entscheid des Verwaltungsgerichts aufzuheben, festzustellen, dass sie beide einen Anspruch auf Bewilligung hätten, und die kantonalen Behörden anzuweisen, die ersuchten Bewilligungen zu erteilen; eventuell sei die Sache zu ergänzenden Abklärungen an das Verwaltungsgericht zurückzuweisen. Zur Begründung wird im Wesentlichen eine Verletzung von Art. 8 EMRK geltend gemacht. Die Staatskanzlei des Kantons Zürich schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Verwaltungsgericht des Kantons Zürich hat auf eine Vernehmlassung verzichtet. Das Bundesamt für Migration beantragt die Abweisung der Beschwerde. F. Parallel zur Beschwerdeerhebung beim Bundesgericht stellten X._ und Y._ ein Revisionsgesuch beim Verwaltungsgericht des Kantons Zürich. Dieses trat darauf am 2. Oktober 2008 nicht ein. Dagegen ging keine Beschwerde beim Bundesgericht ein. Mit ergänzender Eingabe an das Bundesgericht vom 29. Oktober 2008 haben sich die X._ und Y._ jedoch im vorliegenden Verfahren dazu geäussert. G. Mit Verfügung vom 8. Oktober 2008 erteilte das präsidierende Mitglied der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der hängigen Beschwerde die aufschiebende Wirkung. H. Am 18. November 2008 reichten X._ und Y._ dem Bundesgericht ein ergänzendes Dokument zum Gesundheitszustand der ersteren ein.