Sachverhalt:
A. Der nach eigenen Angaben aus Burundi stammende, 1974 geborene X._ (alias L._, alias M._, alias N._) weilt seit Mitte 1998 in der Schweiz. Das damalige Bundesamt für Flüchtlinge (heute: Bundesamt für Migration) wies sein Asylgesuch am 6. Oktober 1998 ab und wies ihn aus der Schweiz weg. Diese Verfügung ist rechtskräftig, doch konnte die Wegweisung aufgrund fehlender Ausweisschriften und Reisedokumente bis heute nicht vollzogen werden. X._ befand sich mehrmals in Ausschaffungshaft (vgl. beispielsweise das Urteil des Bundesgerichts 2A.38/2005 vom 4. Februar 2005). Die Kooperation mit den Behörden verweigerte er (so lehnte er es etwa ab, ein Tonband für eine Sprachanalyse zu besprechen). Seine Staatsbürgerschaft ist nach wie vor ungeklärt.
B. X._ wurde wiederholt straffällig und hiefür wie folgt verurteilt:
- im Jahre 1999: Zu 90 Tagen Gefängnis (bedingt) wegen Missachtung einer Zwangsmassnahme im Ausländerrecht, zu drei Monaten Gefängnis (bedingt) und Busse wegen mehrfachen Verstosses gegen das Betäubungsmittelgesetz und Nichtanzeigen eines Fundes, zu weiteren drei Monaten Gefängnis wegen mehrfachen Verstosses gegen das Betäubungsmittelgesetz,
- im Jahre 2001: Zu drei Monaten Gefängnis wegen Missachtung einer Zwangsmassnahme im Ausländerrecht,
- im Jahre 2002: Zu drei Monaten Gefängnis wegen Diebstahls und Übertretung des Transportgesetzes, zu weiteren drei Monaten und 15 Tagen Gefängnis wegen Missachtung einer Zwangsmassnahme im Ausländerrecht,
- im Jahre 2003: Zu sechs Monaten Gefängnis wegen Missachtung einer Zwangsmassnahme im Ausländerrecht, zu weiteren 12 Wochen Gefängnis wegen mehrfachen Verstössen gegen das Betäubungsmittelgesetz,
- im Jahre 2005: Zu sieben Monaten Gefängnis wegen Missachtung einer Zwangsmassnahme im Ausländerrecht,
- im Jahre 2006: Zu drei Monaten Gefängnis wegen rechtswidrigen Aufenthalts.
C. Am 27. Dezember 2005 gebar die in der Schweiz niederlassungsberechtigte türkische Staatsangehörige Y._ (geb. 1968) den Sohn A._. X._ anerkannte dieses Kind am 1. März 2006 auf dem Zivilstandsamt G._; eine Unterhaltsregelung bestand aber vorerst nicht. Y._ lebt mit zwei volljährigen bzw. kurz vor der Volljährigkeit stehenden Kindern aus einer geschiedenen Ehe und ihrem Sohn A._ in einer Mietwohnung in H._ (Mietzins 2008: monatlich Fr. 1660.--). Sie ist zu 100% invalid und bezieht Rentenleistungen von insgesamt Fr. 4'307.-- pro Monat (2009). Dazu kommen Alimente ihres früheren Ehemannes von Fr. 800.--. Mit X._ ist sie nicht verheiratet. Am 28. September 2009 stellte die Vormundschaftsbehörde der Stadt H._ A._ gemäss <ref-law> (gemeinsames Sorgerecht unverheirateter Eltern) unter die gemeinsame elterliche Sorge der nach eigenen Angaben in einer "eheähnlichen Gemeinschaft" lebenden Partner.
D. Verschiedene Gesuche von X._ um Erteilung einer Aufenthaltsbewilligung bzw. um Kantonswechsel blieben ohne Erfolg. Ein asylrechtliches Wiedererwägungsgesuch, verbunden mit einem Begehren um vorläufige Aufnahme, wies das Bundesamt für Migration am 5. Februar 2007 ab. Die hiegegen beim Bundesverwaltungsgericht erhobene Beschwerde ist noch hängig.
Am 21. November 2008 stellte X._ ein Gesuch um Erteilung einer Aufenthaltsbewilligung zum Verbleib bei Y._ und A._. Mit Verfügung vom 4. März 2009 wies die Sicherheitsdirektion des Kantons Zürich (Migrationsamt) dieses Gesuch ab. Ein hiegegen beim Regierungsrat eingereichter Rekurs blieb erfolglos; und mit Urteil vom 21. Oktober 2009 wies das Verwaltungsgericht des Kantons Zürich die gegen den regierungsrätlichen Beschluss vom 12. August 2009 erhobene Beschwerde ebenfalls ab.
E. Mit Eingabe vom 27. November 2009 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit den Anträgen, den Entscheid des Verwaltungsgerichts des Kantons Zürich vom 21. Oktober 2009 aufzuheben und festzustellen, dass ihm - dem Beschwerdeführer - gestützt auf Art. 8 EMRK ein Anspruch auf eine Aufenthaltsbewilligung zustehe. Dementsprechend sei das Migrationsamt des Kantons Zürich anzuweisen, diese Aufenthaltsbewilligung zu erteilen. Gleichzeitig wird um unentgeltliche Rechtspflege und Verbeiständung ersucht. Die Beiordnung eines unentgeltlichen Rechtsvertreters wird auch für das vorinstanzliche Beschwerdeverfahren verlangt.
Die Staatskanzlei des Kantons Zürich beantragt - für den Regierungsrat - Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich hat auf Vernehmlassung verzichtet. Das Bundesamt für Migration schliesst ebenfalls auf Abweisung der Beschwerde.
F. Mit Verfügung vom 1. Dezember 2009 hat der damalige Abteilungspräsident der Beschwerde - antragsgemäss - aufschiebende Wirkung zuerkannt.

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.
1.2 Aus dem Bundesrecht ergibt sich hier kein Anspruch auf die anbegehrte Aufenthaltsbewilligung: Der Beschwerdeführer ist mit Y._ nicht verheiratet und kann sich daher nicht auf Art. 43 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG, SR 142.20) berufen, wonach u.a. ausländische Ehegatten von Personen mit Niederlassungsbewilligung Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung haben, wenn sie mit diesen zusammenwohnen. Als Anspruchsgrundlage kommt vorliegend einzig Art. 8 EMRK (Anspruch auf Schutz des Familienlebens) in Betracht: 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 diese Garantie 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 sich hier aufhaltende Angehörige muss dabei über ein gefestigtes Anwesenheitsrecht verfügen. Dies ist der Fall, wenn er das Schweizer Bürgerrecht oder eine Niederlassungsbewilligung besitzt oder über eine Aufenthaltsbewilligung verfügt, die ihrerseits auf einem gefestigten Rechtsanspruch beruht (<ref-ruling> E. 3.1 S. 285 f. mit Hinweisen).
Y._ und A._ verfügen beide über die Niederlassungsbewilligung und damit über ein gefestigtes Anwesenheitsrecht. Gemäss den für das Bundesgericht grundsätzlich verbindlichen Feststellungen des Verwaltungsgerichts (vgl. <ref-law>) ist der Beschwerdeführer "offenbar darum bemüht, die Beziehung zu beiden tatsächlich zu leben, soweit dies sein Status als rechtskräftig abgewiesener Asylbewerber zulässt". Nichts Gegenteiliges ergibt sich aus den vorhandenen Akten: Der Beschwerdeführer verfügt zusammen mit der Mutter über das gemeinsame Sorgerecht für das Kind A._; dadurch seien "die Interessen des Kindes gewahrt" (Beschluss der Vormundschaftsbehörde H._ vom 28. September 2009, S. 3). Damit ergibt sich für den Beschwerdeführer jedenfalls aus seiner Beziehung zum Kind A._ ein grundsätzlicher Anwesenheitsanspruch gestützt auf Art. 8 EMRK, und die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist insoweit zulässig.
2. 2.1 Der Anspruch aus Art. 8 EMRK gilt 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.1 S. 147, 153 E. 2.2.1 S. 156; <ref-ruling> E. 2 S. 6 mit Hinweisen). Als zulässiges öffentliches Interesse fällt dabei grundsätzlich auch das Durchsetzen einer restriktiven Einwanderungspolitik im Hinblick auf ein ausgewogenes Verhältnis zwischen schweizerischer und ausländischer Wohnbevölkerung, die Schaffung günstiger Rahmenbedingungen für die Eingliederung der in der Schweiz ansässigen Ausländer und die Verbesserung der Arbeitsmarktstruktur sowie eine möglichst ausgeglichene Beschäftigung in Betracht (<ref-ruling> E. 2.2 S. 147, 153 E. 2.2.1 S. 156).
2.2 Bei der Interessenabwägung im Rahmen von Art. 8 Ziff. 2 EMRK sind die Schwere des begangenen Delikts, der seit der Tat vergangene Zeitraum, das Verhalten des Ausländers während dieser Periode, die Auswirkungen auf die betroffene Person sowie deren familiäre Situation zu berücksichtigen. Unter diesem Gesichtswinkel ist namentlich zu fragen, ob den nahen Familienangehörigen zugemutet werden kann, dem Ausländer, der keine Bewilligung erhält, ins Ausland zu folgen. Die Zumutbarkeit der Ausreise für nahe Familienangehörige ist umso eher zu bejahen, als sein Verhalten seinen Aufenthalt in der Schweiz als unerwünscht erscheinen lässt. Eine allfällige Unzumutbarkeit der Ausreise ist mitabzuwägen, führt aber nicht für sich allein zur Unzulässigkeit einer Bewilligungsverweigerung (<ref-ruling> E. 4b S. 131).
2.3 In die Abwägung mit einfliessen kann vorliegend auch die so genannte, zwar auf Ehegatten von Schweizerinnen zugeschnittene und für Ehegatten von Niedergelassenen verschärft zum Zuge kommende "Zweijahresregel", wonach einem Ausländer, der erstmals um eine Bewilligung ersucht oder nach bloss kurzer, ordnungsgemässer Aufenthaltsdauer deren Erneuerung beantragt, bei einer Verurteilung zu einer Freiheitsstrafe von zwei Jahren (oder länger) in der Regel selbst dann keine Bewilligung mehr erteilt wird, wenn dem Ehepartner die Ausreise un- oder nur schwer zumutbar ist. Es bedarf in solchen Fällen aussergewöhnlicher Umstände, um die Erteilung einer Aufenthaltsbewilligung noch zu rechtfertigen (sog. Reneja-Praxis, <ref-ruling>). Das Bundesgericht weicht auch unter der Herrschaft des seit 1. Januar 2008 in Kraft stehenden Ausländergesetzes nicht grundlegend von dieser Rechtsprechung ab (<ref-ruling>, E. 4.4 S. 382). Bei der Limite von zwei Jahren handelt es sich allerdings nur um einen Richtwert und nicht um eine feste Grenze (<ref-ruling>, a.a.O., 130 II 176 E. 4.1 S. 185 mit Hinweisen). Entscheidend kommt es auf die sich gegenüberstehenden Interessen an.
3. 3.1 Das Verwaltungsgericht hat erwogen, der Beschwerdeführer sei wiederholt straffällig geworden. Nur gerade in der Zeit zwischen dem 4. Juli und dem 30. November 1998 habe er sich rechtmässig in der Schweiz aufgehalten. Der Regierungsrat sei daher zu Recht zum Schluss gekommen, dass die öffentlichen Interessen an einer Fernhaltung des Beschwerdeführers dessen private Interessen an einem Verbleib in der Schweiz überwögen. Y._ sei der unrechtmässige Aufenthalt des Beschwerdeführers ausserdem kaum verborgen geblieben, so dass sie nicht mit einer Aufenthaltsbewilligung für ihn habe rechnen dürfen.
3.2 Der Beschwerdeführer wendet im Wesentlichen ein, die Verweigerung der Aufenthaltsbewilligung sei nicht "als in einer demokratischen Gesellschaft notwendig" (vgl. Art. 8 Ziff. 2 EMRK) zu qualifizieren. So sei zu erwähnen, dass er nie mit Drogen gehandelt habe. Ausserdem stünden 26 von insgesamt 38 Monaten Freiheitsstrafe im Zusammenhang mit seinem "illegalen" Aufenthalt; von krimineller Energie oder gar Gefährlichkeit könne keine Rede sein. Die Urteile gegen ihn lägen ausserdem lange zurück; seit der Geburt seines Sohnes habe er sich "bewährt". Aufgrund der Rechtsprechung des Europäischen Gerichtshofes für Menschenrechte verstosse eine Wegweisung gegen den Verhältnismässigkeitsgrundsatz.
3.3 Zunächst ist festzuhalten, dass es im vorliegenden Verfahren nicht um die Wegweisung des Beschwerdeführers geht, sondern um die Erteilung einer Aufenthaltsbewilligung an diesen. Zwar hat es das Bundesverwaltungsgericht in seiner Zwischenverfügung vom 29. März 2007 abgelehnt, den Vollzug der Wegweisung auszusetzen; in der Hauptsache (Wiedererwägung/vorläufige Aufnahme) hat es aber noch nicht entschieden. Wie die Vorinstanz zutreffend erkannt hat, sind die Vorbringen gegen den Vollzug der Wegweisung deshalb vor dem Bundesverwaltungsgericht geltend zu machen und ist insoweit auf die vorliegende Beschwerde nicht einzutreten.
3.4 Ausgangspunkt und Massstab für die Schwere des Verschuldens und die fremdenpolizeiliche Interessenabwägung ist die vom Strafrichter verhängte Strafe (<ref-ruling>, nicht publ. E. 5.3, 129 II 215 E. 3.1 S. 216). Die Verurteilung zu Freiheitsstrafen von insgesamt fast 38 Monaten deutet auf ein erhebliches Verschulden hin. Die Beteuerungen des Beschwerdeführers, er habe - was die Verurteilungen wegen Betäubungsmitteldelikten betreffe - Drogen bloss für den Eigenkonsum besessen, steht im Widerspruch zur Aktenlage (vgl. etwa das Urteil des Bezirksgerichts Zürich vom 24. August 1999, S. 3 und 4, sowie Urteil des Bezirksgerichts Bischofszell vom 25. April 2003, S. 2). Zwar liegen mehrere Verurteilungen bereits längere Zeit zurück und trifft es zu, dass nach <ref-law> (in der seit 1. Januar 2007 in Kraft stehenden Fassung) aus dem Strafregister entfernte Urteile dem Betroffenen nicht mehr entgegengehalten werden dürfen. Für die ausländerrechtliche Interessenabwägung ist aber das Verwertungsverbot gemäss <ref-law> insofern zu relativieren, als es den Fremdenpolizeibehörden nicht verwehrt ist, strafrechtlich relevante Daten, die sich in ihren Akten befinden oder ihnen anderweitig bekannt sind bzw. werden, selbst nach deren Löschung im Strafregister in die Beurteilung des Verhaltens des Ausländers während seiner gesamten Anwesenheit in der Schweiz einzubeziehen (vgl. Urteil 2C_332/2009 vom 16. November 2009, E. 3.3). Die Drogendelikte und die wiederholten Verstösse des Beschwerdeführers gegen die mehrfach verfügten ausländerrechtlichen Administrativmassnahmen (Ein- und Ausgrenzungen), aber auch der Tatablauf vom 20. Juli 2001 beim Bestehlen des Minibar-Angestellten in der Bahn zeugen von krimineller Energie und einer ausgeprägten Gleichgültigkeit und Geringschätzung gegenüber der schweizerischen (Rechts-)Ordnung. Dieser Eindruck wird durch die Tatsache verstärkt, dass der Beschwerdeführer seiner Wegweisung nie Folge leistete und sich schon vor der Geburt des Kindes A._ jahrelang illegal in der Schweiz aufhielt. Aufgrund dieser Umstände erhellt ohne weiteres, dass nach wie vor ein erhebliches öffentliches Interesse daran besteht, dem Beschwerdeführer den weiteren Aufenthalt im Land zu verweigern. Er ist im Übrigen nicht hier aufgewachsen oder bereits im Kindesalter in die Schweiz gekommen und kann daher aus dem in seiner Beschwerde mehrfach angerufenen Urteil des EGMR "Emre gegen die Schweiz" (Nr. 42034/04) vom 22. Mai 2008 nichts zu seinen Gunsten ableiten.
3.5 Was das Kind A._ betrifft, fällt die gelebte Beziehung in der Interessenabwägung zu Gunsten des Beschwerdeführers massgeblich ins Gewicht. Ihm ist zugute zu halten, dass er einen "Betreuungsanteil" übernimmt, und zwar durch "Besuche bei der Mutter und A._ in H._" (vgl. die von der Vormundschaftsbehörde H._ am 28. September 2009 genehmigte Vereinbarung über die Betreuung und den Unterhalt, S. 2). Er hat mit A._ aber nie in Familiengemeinschaft gelebt und leistet für ihn keinen Unterhalt. A._ befindet sich auch noch in einem anpassungsfähigen Alter; es wäre ihm zuzumuten, dem Beschwerdeführer ins Ausland zu folgen (vgl. <ref-ruling> E. 2b S. 67). Dasselbe gilt für die Partnerin, die nicht davon ausgehen durfte, ihre Beziehung auf Dauer in der Schweiz leben zu können. Die Behauptung des Beschwerdeführers, wegen fehlender Papiere sei er gar nicht in der Lage, auszureisen (vgl. S. 8 der Beschwerdeschrift), erscheint im Übrigen unbehelflich; er ist in diesem Zusammenhang an seine weiter fortbestehende Mitwirkungspflicht bei der Papierbeschaffung zu erinnern, die er in der Vergangenheit wiederholt verletzt hat (vgl. vorne lit. "A" und Urteil des Bundesgerichts 2A.38/2005 vom 4. Februar 2005, E. 2.2).
3.6 Selbst eine Heirat der Konkubinatspartner würde nichts ändern: Der Anspruch des Beschwerdeführers auf Erteilung einer Aufenthaltsbewilligung (vgl. Art. 43 Abs. 1 AuG) wäre in diesem Fall zumindest mit dem Widerrufsgrund von Art. 62 lit. c AuG (wiederholter Verstoss gegen die öffentliche Ordnung und Sicherheit) behaftet, allenfalls - zumal die Erwerbsmöglichkeiten des Beschwerdeführers, der selber einräumt, "Analphabet" zu sein und über ein "niedriges Bildungsniveau" zu verfügen (vgl. Beschwerde an den Regierungsrat, S. 11), beschränkt sind - auch mit dem Widerrufsgrund von Art. 62 lit. e AuG (Sozialhilfeabhängigkeit).
4. Die vom Beschwerdeführer beanstandete Interessenabwägung erweist sich damit im Lichte von Art. 8 Ziff. 2 EMRK als konventionskonform, was bereits im regierungsrätlichen Rekursentscheid in rechtlich zutreffender Weise und mit ausführlichen Hinweisen auf die einschlägige Rechtsprechung zum Ausdruck kam. Das Verwaltungsgericht hat deshalb auch das vom Beschwerdeführer gestellte Gesuch um unentgeltliche Rechtspflege und Verbeiständung zu Recht abgewiesen.
5. Dies führt zur Abweisung der Beschwerde, soweit darauf eingetreten werden kann.
Da der angefochtene Entscheid im Einklang mit der veröffentlichten Rechtsprechung des Bundesgerichts zu Art. 8 EMRK steht, konnte der Beschwerdeführer nicht ernsthaft mit der Gutheissung seiner Anträge rechnen. Seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist deshalb nicht zu entsprechen (<ref-law>); seiner finanziellen Lage ist aber bei der Bemessung der Gerichtskosten Rechnung zu tragen (<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 dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, der Sicherheitsdirektion, dem Regierungsrat und dem Verwaltungsgericht (4. Kammer) des Kantons Zürich sowie dem Bundesamt für Migration und dem Bundesverwaltungsgericht schriftlich mitgeteilt.
Lausanne, 25. Mai 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Klopfenstein