Sachverhalt:
A. Gestützt auf die Heirat mit einer Schweizer Bürgerin im Februar 2003 erhielt der ursprünglich aus Rumänien stammende X._ (geb. 1965) eine zuletzt bis zum 20. Februar 2005 verlängerte Aufenthaltsbewilligung für den Kanton Zürich. Nachdem sich die Eheleute im Oktober 2004 getrennt hatten, lehnte die Sicherheitsdirektion dieses Kantons am 11. Dezember 2006 das Gesuch um weitere Verlängerung der Aufenthaltsbewilligung ab. Dagegen erhob X._ Rekurs. Im Frühjahr 2007 wurde seine Ehe rechtskräftig geschieden. Am 27. Mai 2009 wies der Regierungsrat des Kantons Zürich den Rekurs ab. Auch die anschliessende Beschwerde an das Verwaltungsgericht des Kantons Zürich blieb erfolglos.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 20. Januar 2010 beantragt X._ dem Bundesgericht, das im Kanton zuletzt ergangene Urteil des Verwaltungsgerichts vom 18. November 2009 sowie die vorangegangenen Entscheide des Regierungsrates und der Sicherheitsdirektion aufzuheben. Letztere sei anzuweisen, seine Aufenthaltsbewilligung zu verlängern, eventualiter ihm eine Aufenthaltsbewilligung als Staatenloser zu erteilen. Subeventualiter sei die Sicherheitsdirektion anzuweisen, die Sache mit Antrag auf Erteilung einer vorläufigen Aufnahme, statt der Ausdehnung der Wegweisung, an das Bundesamt für Migration zu überweisen.
Das Verwaltungsgericht beantragt, die Beschwerde abzuweisen, soweit auf sie einzutreten sei. Das Bundesamt für Migration ersucht um Abweisung der Beschwerde. Die Sicherheitsdirektion und der Regierungsrat haben sich nicht vernehmen lassen.

Erwägungen:
1. Der Beschwerdeführer stellte seine Gesuche erstmals vor dem Inkrafttreten des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) am 1. Januar 2008. Daher ist im vorliegenden Verfahren - wie die Vorinstanzen richtig festhalten - gemäss Art. 126 Abs. 1 AuG materiell noch das vor dem letztgenannten Datum geltende Ausländerrecht anwendbar.
2. Der Beschwerdeführer beantragt dem Bundesgericht in verfahrensrechtlicher Hinsicht, das Verfahren zu sistieren, bis das Bundesverwaltungsgericht über seine Beschwerde gegen eine Verfügung des Bundesamts für Migration vom 17. Dezember 2009 entschieden hat. Er macht insoweit geltend, er habe gemäss Art. 31 AuG einen Anspruch auf Erteilung der Aufenthaltsbewilligung, falls seine Staatenlosigkeit anerkannt werden sollte.
Der Beschwerdeführer war mit einem Wiedererwägungsgesuch betreffend die Feststellung seiner Staatenlosigkeit an das Bundesamt für Migration gelangt. Dieses war darauf nicht eingetreten. Dagegen hat der Beschwerdeführer beim Bundesverwaltungsgericht Beschwerde eingereicht, welche dort offenbar noch hängig ist.
Das Bundesgericht kann aus Gründen der Zweckmässigkeit das Verfahren aussetzen, insbesondere wenn das Urteil von der Entscheidfindung in einem anderen Rechtsstreit beeinflusst werden kann (<ref-law> in Verbindung mit <ref-law>). Sollte die Staatenlosigkeit des Beschwerdeführers festgestellt werden, könnte dieser nach neuem Recht (Art. 31 AuG) eventuell eine Aufenthaltsbewilligung erhalten, so dass das aktuelle bundesgerichtliche Verfahren möglicherweise gegenstandslos würde. Es ist allerdings nicht absehbar, wann das Verfahren zur Feststellung der Staatenlosigkeit zum Abschluss gelangen wird. Ausserdem ist die Sache beim Bundesgericht entscheidungsreif. Diese hängt insbesondere nicht vom Ausgang des Rechtsstreits über die Staatenlosigkeit ab (s. auch E. 4.3 hienach). Deshalb ist das Sistierungsgesuch abzuweisen.
3. 3.1 Auf dem Gebiet des Ausländerrechts ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gemäss Art. 83 lit. c Ziff. 2-5 BGG unzulässig gegen Entscheide über die Wegweisung, die vorläufige Aufnahme, über Abweichungen von den Zulassungsvoraussetzungen sowie über Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. Daher ist auf die Eingabe nicht einzutreten, soweit der Beschwerdeführer Antrag stellt auf Weiterleitung an das Bundesamt für Migration wegen vorläufiger Aufnahme sowie auf eine Bewilligung nach Ermessen (u.a. gemäss Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer [ANAG; BS 1 121] sowie Art. 13 lit. f und Art. 36 der Verordnung vom 6. Oktober 1986 über die Begrenzung der Zahl der Ausländer [BVO; AS 1986 1791]). Diesbezüglich scheidet auch eine Behandlung als subsidiäre Verfassungsbeschwerde aus, da keine geeigneten Rügen geltend gemacht werden. Die behauptete willkürliche Rechtsanwendung kann insoweit nicht gerügt werden. Denn die erwähnten Zulassungsschranken würden auf diese Weise praktisch unterlaufen und die für diese Rechtsgebiete angestrebte Entlastung des Bundesgerichts weitgehend in Frage gestellt, ohne dass für den Rechtsschutz der Betroffenen viel gewonnen wäre (vgl. Art. 113, 115, 116 sowie 117 in Verbindung mit <ref-law>; <ref-ruling>, insbes. E. 6 S. 197 ff.; <ref-ruling> E. 1.4 S. 222; <ref-ruling> E. 1a S. 235). Der in diesem Zusammenhang gestellte Antrag, ein Gutachten bei der Schweizerischen Flüchtlingshilfe einzuholen, ist damit von vornherein unbeachtlich.
Auf die rechtzeitig eingereichte Beschwerde ist mithin nur einzutreten, soweit der Beschwerdeführer einen Rechtsanspruch auf eine Bewilligung geltend machen kann. Wegen des Devolutiveffektes ist allerdings auch in dieser Hinsicht der Antrag unzulässig, die dem Urteil des Verwaltungsgerichts unmittelbar vorangegangenen Entscheide des Regierungsrates und der Sicherheitsdirektion aufzuheben (vgl. <ref-ruling> E. 1.4 S. 144).
4. 4.1 Der Beschwerdeführer macht einen Rechtsanspruch aus Familienleben gestützt auf Art. 8 EMRK und <ref-law> geltend. Er beruft sich darauf, dass seine aus der Ehe mit der Schweizer Bürgerin hervorgegangene minderjährige Schweizer Tochter A._ (geb. 2003), über welche allein die Kindsmutter das Sorgerecht ausübt, in der Schweiz lebe.
Der Beschwerdeführer rügt, er habe entgegen der Darstellung der Vorinstanz nicht damit rechnen müssen, dass er bei Trennung der Eheleute die Beziehung zur Tochter nicht mit Sicherheit werde aufrechterhalten können. Wohl ist die diesbezügliche Argumentation des Verwaltungsgerichts nicht ausschlaggebend. Allerdings haben die Vorinstanzen auch festgestellt, dass der Beschwerdeführer keine besonders enge Beziehung affektiver und wirtschaftlicher Art zu seiner Tochter unterhält (zu dieser Voraussetzung vgl. Urteil des Bundesgerichts 2D_99/2008 vom 16. Februar 2009 E. 2, insb. E. 2.3; s. zudem <ref-ruling> E. 3 S. 4 ff., 22 E. 4 S. 24 ff.). Darauf geht der Beschwerdeführer mit keinem Wort ein und legt namentlich nicht dar, dass diese Feststellung offensichtlich falsch sei (vgl. Art. 97 und 105 BGG). Er verweist zwar pauschal auf seine Ausführungen in der Beschwerdeschrift an das Verwaltungsgericht. Das genügt den Rüge- und Begründungsanforderungen der Art. 42 und 106 Abs. 2 BGG indes nicht (vgl. Urteile des Bundesgerichts 4A_56/2009 vom 11. August 2009 E. 4.1 und 5A_199/2009 vom 6. Mai 2009 E. 1.2). Davon abgesehen ist aber auch den dortigen Ausführungen nicht zu entnehmen, dass die Beziehung zur Tochter besonders eng wäre. Mithin ist nicht zu beanstanden, dass die Vorinstanzen dem Beschwerdeführer einen Anspruch aus Familienleben mit Blick auf seine Tochter verneint haben.
4.2 Unter Berufung auf Art. 8 EMRK und <ref-law> macht der Beschwerdeführer auch einen Anspruch aus Privatleben geltend. Die Vorinstanz führt unter Hinweis auf die einschlägige Rechtsprechung des Bundesgerichts aus, es sei nicht ersichtlich, dass der Beschwerdeführer besonders intensive Bindungen oder soziale Beziehungen zur Schweiz habe (vgl. dazu allg. <ref-ruling> E. 3.2.1 S. 286 mit Hinweisen). Der Beschwerdeführer begnügt sich damit, diesen Ausführungen seine Sichtweise gegenüberzustellen. Doch weder aus der Dauer seines Aufenthaltes in der Schweiz, in die er seit 1988 wiederholt einreiste und wo er zwei Asylgesuche stellte, noch sonst wie ergibt sich, dass er über eine normale Integration hinaus mit der Schweiz verbunden wäre. Er gelangte in die Schweiz erst als Erwachsener. Das eheliche Zusammenleben war nur von kurzer Dauer. Während seines Aufenthaltes lebte er in erheblichem Umfang von Sozialhilfe. Es ist schon fraglich, ob er sich überhaupt integriert hat. Demzufolge durften die Vorinstanzen auch unter dem Blickwinkel des Schutzes des Privatlebens einen Anspruch auf eine Bewilligung verneinen.
4.3 Schliesslich beruft sich der Beschwerdeführer auf den bereits erwähnten Art. 31 AuG (s. E. 2 hievor). Wie ausgeführt, ist hier das neue Ausländerrecht jedoch noch nicht anwendbar (E. 1 hievor). Das alte Recht vermittelt keinen Bewilligungsanspruch für Staatenlose. Das gilt auch für das Übereinkommen vom 28. September 1954 über die Rechtsstellung der Staatenlosen (SR 0.142.40). Entgegen der Ansicht des Beschwerdeführers ist es weder rechtsmissbräuchlich noch verstösst es gegen Treu und Glauben oder das Rechtsverweigerungsverbot, im vorliegenden Verfahren weiterhin auf das alte Ausländerrecht abzustellen. Sollte die Staatenlosigkeit des Beschwerdeführers anerkannt werden, wird dieser einen neuen Antrag stellen können, den die Behörden dann gestützt auf Art. 31 AuG werden behandeln müssen (vgl. BGE 2C_490/2009 vom 2. Februar 2010 E. 2).
Falls die Staatenlosigkeit nicht anerkannt werden sollte, würde sich die Frage stellen, ob dem Beschwerdeführer, der aus Rumänien stammt, gestützt auf das Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (Freizügigkeitsabkommen, FZA; SR 0.142.112.681) eine Bewilligung zu erteilen ist. Offenbar ist der Beschwerdeführer in der Schweiz erwerbstätig und könnte damit einen Freizügigkeitstatbestand erfüllen. Zudem ist das Protokoll vom 27. Mai 2008 über die Erweiterung des Abkommens auf Rumänien (SR 0.142.112.681.1) am 1. Juni 2009 in Kraft getreten.
Zwar gilt bezüglich des Freizügigkeitsabkommens der Grundsatz, dass für Verfahren, die bei seinem Inkrafttreten hängig sind, bereits das neue Recht anzuwenden ist (<ref-ruling> E. 3.3 in fine S. 258; <ref-ruling> E. 3.1 S. 5). Das trifft jedoch für das bundesgerichtliche Verfahren nicht zu, wenn hierbei von einer Ausgangslage oder einem Sachverhalt auszugehen ist, der sich nicht mit demjenigen deckt, der dem kantonalen Urteil zugrunde liegt (vgl. Urteile 2A.270/2006 vom 19. Mai 2006 und 2C_22/ 2009 vom 5. Oktober 2009 E. 2.2.1). Der Beschwerdeführer beruft sich darauf, staatenlos zu sein. Er macht weder vor Bundesgericht noch bei den Vorinstanzen geltend, als erwerbstätiger Rumäne die Voraussetzungen für eine Aufenthaltsgewährung gemäss dem Freizügigkeitsabkommen zu erfüllen. Daher hat das Bundesgericht von einer materiellen Beurteilung nach dem Abkommen abzusehen. Auch der Vorinstanz kann nicht vorgeworfen werden, auf eine entsprechende Prüfung verzichtet zu haben, da der Beschwerdeführer sich darauf beruft, staatenlos und gerade nicht rumänischer Staatsangehöriger zu sein.
Sollte die Staatenlosigkeit definitiv verneint werden, wäre der Beschwerdeführer aufgrund seiner Herkunft aber als Rumäne zu behandeln. Insoweit könnte er die aus dem Freizügigkeitsabkommen fliessenden Ansprüche geltend machen. Auf ein von ihm dann noch zu stellendes Gesuch, wobei er bzw. sein Arbeitgeber - vor allem mit Blick auf die Übergangsbestimmungen des Art. 10 FZA - die dazu erforderlichen Angaben und Unterlagen beizubringen hätte, müssten die zuständigen Behörden eintreten.
5. Nach dem Dargelegten ist die Beschwerde abzuweisen, soweit auf sie überhaupt einzutreten ist. Diesem Ausgang entsprechend hat der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens zu tragen (Art. 65 f. BGG). Sein Antrag auf unentgeltliche Rechtspflege und Verbeiständung ist - wie schon bei der Vorinstanz - abzuweisen, da auch das beim Bundesgericht eingereichte Rechtsbegehren keine ernsthaften Erfolgsaussichten besass (vgl. <ref-law>; <ref-ruling> E. 5 S. 616). Parteientschädigungen werden nicht geschuldet (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Das Sistierungsgesuch wird abgewiesen.
2. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
3. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
4. Die Gerichtskosten von Fr. 1'500.-- werden dem Beschwerdeführer auferlegt.
5. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 14. Juni 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Merz