Sachverhalt:
A. X._ (geb. 1975) stammt aus Ghana. Am 13. März 2001 hatte er die Schweizer Bürgerin Y._ (geb. 1968) geheiratet. Bereits im Jahre 1998 war ihr gemeinsamer Sohn A._ zur Welt gekommen. Am 4. August 2004 wurde die Ehe auf Begehren der Ehefrau gerichtlich getrennt. X._ erhielt ein Besuchsrecht gegenüber seinem Sohn zugesprochen. A._ wächst seit Ende Oktober 2004 bei Pflegeeltern im Kanton Thurgau auf.
Mit Beschluss vom 24. August 2005 entzog die Vormundschaftsbehörde Kreuzlingen X._ bis auf weiteres das Besuchsrecht. Gegen diesen Beschluss erhob X._, vertreten durch Rechtsanwältin Sabine Geissbühler, am 8. September 2005 Rekurs an das kantonale Departement für Justiz und Sicherheit.
B. Wenige Wochen vorher, am 5. Juli 2005, hatte das Ausländeramt (heute: Migrationsamt) des Kantons Thurgau X._ zu beabsichtigten fremdenpolizeilichen Massnahmen (Nichtverlängerung der Aufenthaltsbewilligung, Weg-/Ausweisung) das rechtliche Gehör eingeräumt. Rechtsanwältin Sabine Geissbühler nahm mit Eingabe vom 18. August 2005 im Namen von X._ in ablehnendem Sinne hiezu Stellung und stellte für ihren Klienten gleichzeitig ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung. Am 3. November 2005 sistierte das Ausländeramt daraufhin das "fremdenpolizeiliche Wegweisungsverfahren" bis zum Vorliegen des Departementsentscheides zur Neuregelung des Besuchsrechts. Beim Departement blieb diese letztgenannte Angelegenheit hängig.
C. Mit Beschluss vom 8. Mai 2007 räumte die Vormundschaftsbehörde Kreuzlingen X._ das Recht ein, seinen Sohn unter fachlicher Aufsicht sehen zu können. Hiegegen wiederum wehrten sich die Kindsmutter/Ehefrau und die Pflegeeltern. Ihre Rekurse wurden vom Departement für Justiz und Sicherheit gutgeheissen. Die von X._ gegen diesen Departementsentscheid erhobene Beschwerde wies das Verwaltungsgericht des Kantons Thurgau mit Entscheid vom 21. Mai 2008 ab.
D. Inzwischen, am 2. Juli 2007, hatte das Migrationsamt Rechtsanwältin Sabine Geissbühler angeschrieben und mitgeteilt, es beabsichtige, das "sistierte fremdenpolizeiliche Wegweisungsverfahren (...) fortzusetzen, ohne den Beschwerdeentscheid des DJS betreffend Besuchsrechtsregelung weiter abzuwarten", wozu ihrem Mandanten "im Rahmen des laufenden rechtlichen Gehörs (Schreiben vom 5. Juli 2005)" Gelegenheit geboten werde, sich zu äussern. Rechtsanwältin Geissbühler reichte am 13. Juli 2007 eine Stellungnahme ein. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung hielt sie ausdrücklich aufrecht.
E. Mit Entscheid vom 18. Juli 2007 nahm das Migrationsamt das sistierte fremdenpolizeiliche Verfahren wieder auf, verlängerte die am 20. Mai 2007 abgelaufene Aufenthaltsbewilligung von X._ nicht mehr und wies diesen aus der Schweiz weg. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wies das Amt mit der Begründung ab, es sei einzig darum gegangen, im Rahmen des rechtlichen Gehörs eine (fakultative) Stellungnahme abzugeben.
Gegen diesen Entscheid erhob X._ erfolglos Rekurs beim kantonalen Departement für Justiz und Sicherheit (Entscheid vom 2. Juli 2008). Die Gewährung des prozessualen Armenrechts lehnte das Departement mit der Begründung ab, das Rekursverfahren sei von Anfang an aussichtslos gewesen.
In der Zwischenzeit hatte das Bezirksgericht Kreuzlingen das von der Ehefrau Y._ am 3. November 2006 gestellte Scheidungsbegehren gutgeheissen und die Ehe geschieden (Urteil vom 17. Dezember 2007). Im Scheidungsverfahren gegen seine Frau war X._ im Rahmen der unentgeltlichen Rechtspflege und Verbeiständung ebenfalls von Rechtsanwältin Geissbühler vertreten worden.
F. Nun gelangte X._ erneut ans Verwaltungsgericht: Mit Beschwerde vom 5. September 2008 beantragte er die Aufhebung des ausländerrechtlich begründeten Departementsentscheides vom 2. Juli 2008 im Kostenpunkt und verlangte sowohl für die vorinstanzlichen Verfahren wie auch für das Beschwerdeverfahren vor Verwaltungsgericht die unentgeltliche Rechtspflege und Verbeiständung.
Mit Entscheid vom 5. November 2008 hiess das Verwaltungsgericht die Beschwerde gut und bestellte Rechtsanwältin Sabine Geissbühler zur unentgeltlichen Rechtsvertreterin von X._. Unter diesem Titel verpflichtete das Gericht das Departement, der Anwältin "für das Rekursverfahren" ein Honorar von Fr. 2'200.-- zu bezahlen; für das Verfahren vor dem Verwaltungsgericht setzte es die Entschädigung auf Fr. 1'200.-- fest. Zur Frage des prozessualen Armenrechts im Verfahren vor dem Migrationsamt äusserte sich das Gericht nicht.
G. Rechtsanwältin Geissbühler stellte daher am 17. November 2008 beim Verwaltungsgericht ein Erläuterungsgesuch und bat um Stellungnahme.
Mit Schreiben vom 21. November 2008 teilte ihr der Verwaltungsgerichtspräsident mit, ihrem Mandanten sei für das Verfahren vor dem Migrationsamt keine Entschädigung zugesprochen worden. Der Grund dafür liege in § 80 Abs. 5 des kantonalen Verwaltungsrechtspflegegesetzes, wonach in erstinstanzlichen Verwaltungsverfahren "grundsätzlich keine Parteientschädigungen zugesprochen" würden. Im Entscheid vom 5. November 2008 sei die genannte Norm allerdings wegen eines redaktionellen Versehens nicht erwähnt worden, wofür sich das Verwaltungsgericht entschuldige.
H. Rechtsanwältin Sabine Geissbühler führt mit Eingabe vom 17. Dezember 2008 namens und im Auftrag von X._ Beschwerde beim Bundesgericht mit den Anträgen, den Entscheid des Verwaltungsgerichts des Kantons Thurgau vom 5. November 2008 aufzuheben bzw. in dem Sinne zu ergänzen, dass dem Beschwerdeführer auch für das erstinstanzliche Verfahren vor dem Migrationsamt die unentgeltliche Prozessführung und Verbeiständung zu gewähren sei; eventuell sei die Sache zur Ergänzung zurückzuweisen. Gleichzeitig wird auch für das Verfahren vor Bundesgericht um unentgeltliche Rechtspflege und Verbeiständung ersucht.
Das Migrationsamt des Kantons Thurgau beantragt, die Beschwerde abzuweisen. Das Departement für Justiz und Sicherheit und das Verwaltungsgericht des Kantons Thurgau stellen denselben Antrag. Das Bundesamt für Migration hat auf Vernehmlassung verzichtet.

Erwägungen:
1. 1.1 Angefochten ist ein Endentscheid eines kantonalen Verwaltungsgerichts als letzter kantonaler Instanz (<ref-law>) in einer Angelegenheit des öffentlichen Rechts (<ref-law>), welche nicht unter eine der in <ref-law> erwähnten Ausnahmen fällt. Es geht einzig noch um die Frage, ob dem Beschwerdeführer im erstinstanzlichen Verfahren vor dem Migrationsamt die unentgeltliche Rechtspflege und Verbeiständung hätte gewährt werden müssen. In diesem Verfahren war es um die Verlängerung seines Anwesenheitsrechtes in der Schweiz gegangen, auf welche(s) er aufgrund des Besuchsrechts gegenüber seinem Kind einen grundsätzlichen Anspruch hatte (Art. 8 EMRK, vgl. <ref-ruling> E. 1 S. 3 sowie [für den Fall, dass sich der eine Elternteil das Besuchsrecht gegen den Widerstand des anderen erstreiten muss] Urteil 2A.428/2000 vom 9. Februar 2001). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist somit grundsätzlich zulässig. Der Beschwerdeführer erfüllt die Legitimationsvoraussetzungen gemäss <ref-law>.
1.2 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. Das Bundesgericht prüft, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), 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 hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. 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).
Die Feststellung des Sachverhalts kann nur gerügt werden, wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht.
2. 2.1 Der Beschwerdeführer rügt die Verletzung von <ref-law>, mithin des Anspruchs auf unentgeltliche Rechtspflege und Verbeiständung. Dieser Anspruch wird in erster Linie durch das kantonale Prozessrecht geregelt. Unabhängig davon besteht ein solcher Anspruch unmittelbar aufgrund von <ref-law>. Die Auslegung und Anwendung der kantonalen Gesetzesbestimmungen über den Anspruch auf unentgeltliche Rechtspflege und Verbeiständung prüft das Bundesgericht unter dem Gesichtswinkel des Willkürverbots. Ob der durch die Bundesverfassung garantierte Anspruch verletzt ist, untersucht es in rechtlicher Hinsicht frei; soweit es um tatsächliche Feststellungen der kantonalen Instanz geht, ist seine Prüfungsbefugnis auf Willkür beschränkt (<ref-ruling> E. 2.1 mit Hinweisen).
2.2 Die kantonalen Bestimmungen, deren willkürliche Anwendung der Beschwerdeführer rügt und auf die sich das Verwaltungsgericht im angefochtenen Entscheid sowie in der Antwort seines Präsidenten auf das Erläuterungsgesuch und in der Vernehmlassung an das Bundesgericht bezogen hat, finden sich im thurgauischen Gesetz vom 23. Februar 1981 über die Verwaltungsrechtspflege (VRG). § 81 VRG lautet:
1 Einem bedürftigen Beteiligten kann auf Antrag die unentgeltliche Rechtspflege bewilligt werden, sofern das Verfahren nicht als aussichtslos erscheint.
2 Sofern es die Umstände erfordern, namentlich im Verfahren vor Verwaltungsgericht, kann einem Beteiligten ein für ihn unentgeltlicher, im kantonalen Anwaltsregister eingetragener Anwalt bewilligt werden.
§ 80 VRG (in der Fassung vom 29. September 1997; Marginale: "Ausseramtliche Kosten") hat, soweit hier interessierend, folgenden Wortlaut:
1 Im Verfahren vor dem Verwaltungsgericht oder dem Regierungsrat besteht in der Regel Anspruch auf Ersatz der ausseramtlichen Kosten.
2 - 4 (...).
5 In den übrigen Verwaltungsverfahren werden keine Parteientschädigungen zugesprochen.
2.3 Die Frage, ob im erstinstanzlichen (Verwaltungs-)Verfahren ein Anspruch auf Parteientschädigung besteht, muss - anders als dies das Verwaltungsgericht tut - von der Frage, ob einer bedürftigen Partei die unentgeltliche Rechtspflege zu bewilligen bzw. ein unentgeltlicher Rechtsbeistand zu bestellen ist, getrennt werden. Diesbezüglich besteht - unter den nachgenannten Voraussetzungen - auch im nichtstreitigen Verwaltungsverfahren ein Anspruch unmittelbar aus <ref-law> (<ref-ruling> E. 2.3 S. 226 f. mit Hinweisen). Der Anspruch gilt für jegliches staatliche Verfahren, in das der Betroffene einbezogen ist; auf die Rechtsnatur des in Frage stehenden Verfahrens kommt es nicht an (<ref-ruling> E. 3a S. 265; <ref-ruling> E. 2a/bb S. 62).
2.4 Voraussetzung für den Anspruch auf unentgeltliche Rechtspflege ist das Vorliegen von Bedürftigkeit des Betroffenen (vgl. dazu <ref-ruling> E. 2.5.1), die Nicht-Aussichtslosigkeit der Rechtssache (dazu <ref-ruling> E. 2.3.1) und die Notwendigkeit der Verbeiständung (dazu <ref-ruling> E. 2.5.2).
Die beiden ersten Voraussetzungen sind vorliegend nicht (mehr) streitig und gehen auch aus den Akten hervor (vgl. angefochtener Entscheid, S. 5 und S. 7). Es geht noch um die Notwendigkeit der Verbeiständung.
2.5 Ein Anspruch auf unentgeltliche Verbeiständung besteht, soweit sie für die Wahrung der Rechte notwendig ist und der Betroffene seine Sache - auf sich allein gestellt - nicht sachgerecht und hinreichend wirksam vertreten kann. Die Notwendigkeit der Verbeiständung beurteilt sich aufgrund der Gesamtheit der konkreten Umstände; dazu zählen insbesondere die Schwere der Betroffenheit in grundlegenden Interessen, die tatsächlichen und rechtlichen Schwierigkeiten, die anwendbaren Verfahrensvorschriften sowie die Fähigkeit, sich im Verfahren zurechtzufinden (<ref-ruling> E. 2.5.2, vgl. zum Ganzen GEROLD STEINMANN, in: St. Galler Kommentar BV, 2. Auflage 2008, Rz. 36 ff. zu <ref-law>).
3. 3.1 Vorliegend ist massgebend, dass ausländerrechtlich eine komplexe Situation vorlag: Es ging um die vom Migrationsamt dem Beschwerdeführer gegenüber angedrohte Beendigung des Aufenthaltsrechtes, welches Verfahren dann allerdings während fast zwei Jahren sistiert blieb (vgl. vorne lit. B und lit. E). Gleichzeitig waren mehrere andere Verfahren hängig, was der Beschwerdeführer aber nicht alleine zu vertreten hat: Das laufende Scheidungsverfahren war von seiner Ehefrau eingeleitet worden (vorne lit. E, am Ende), welche sich, zusammen mit den Pflegeeltern des gemeinsamen Kindes, auch gegen die von der Vormundschaftsbehörde angeordnete Neugestaltung des Besuchsrechts zur Wehr gesetzt hatte (vorne lit. C). Der Streit um die Ausübung des Besuchsrechts war zuvor schon - ebenfalls während fast zwei Jahren - beim Departement für Justiz und Sicherheit hängig gewesen (vorne lit. A und B), was das Migrationsamt offenbar dazu veranlasst hatte, das Verfahren zur Beendigung des Aufenthaltsrechts fortzusetzen, ohne den entsprechenden Departementsentscheid abzuwarten (vorne lit. D).
3.2 Aufgrund der gesamten Umstände dieses aussergewöhnlichen Einzelfalls lässt sich nicht sagen, dass es dem Beschwerdeführer möglich gewesen wäre, sich im fremdenpolizeilichen Verfahren um die Beendigung seines Aufenthaltsrechts selber zurechtzufinden. Es gilt insbesondere zu berücksichtigen, dass dieses Verfahren lange Zeit in der Schwebe blieb und sein Ausgang von verschiedenen anderen, ebenfalls laufenden Verfahren abhängig war, die der Beschwerdeführer nicht selber angestrengt hatte und auf deren Verlauf er selber nur wenig Einfluss nehmen konnte. Er war daher schon im erstinstanzlichen Verwaltungsverfahren vor dem Migrationsamt auf den Beizug anwaltlicher Vertretung angewiesen. Das entsprechende Gesuch hatte er im Übrigen bereits mit der Einreichung der ersten Eingabe stellen lassen (vorne lit. B).
4. Die Beschwerde erweist sich nach dem Gesagten als begründet; sie ist gutzuheissen.
Heisst das Bundesgericht die Beschwerde gut, so entscheidet es in der Sache selbst oder weist diese zu neuer Beurteilung an die Vorinstanz zurück. Es kann die Sache auch an die Behörde zurückweisen, die als erste Instanz entschieden hat (<ref-law>).
Vorliegend erscheint es angezeigt, die Sache an das Verwaltungsgericht zurückzuweisen, damit dieses dem Beschwerdeführer für das ausländerrechtliche Verfahren vor dem Migrationsamt einen unentgeltlichen Rechtsbeistand bestelle.
Bei diesem Ausgang sind keine Gerichtskosten zu erheben (<ref-law>). Hingegen hat der Kanton Thurgau die Rechtsvertreterin des Beschwerdeführers für das bundesgerichtliche Verfahren angemessen zu entschädigen (<ref-law>). Damit wird das für dieses Verfahren gestellte Gesuch um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen.
2. Die Sache wird zur Bestellung eines unentgeltlichen Rechtsbeistandes im Verfahren vor dem Migrationsamt an das Verwaltungsgericht des Kantons Thurgau zurückgewiesen.
3. Es werden keine Gerichtskosten erhoben.
4. Der Kanton Thurgau hat die Rechtsvertreterin des Beschwerdeführers für das bundesgerichtliche Verfahren mit Fr. 1'200.-- zu entschädigen.
5. Das Gesuch um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
6. Dieses Urteil wird dem Beschwerdeführer, dem Migrationsamt und dem Departement für Justiz und Sicherheit sowie dem Verwaltungsgericht des Kantons Thurgau und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 2. Juni 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Klopfenstein