Sachverhalt:
A. X._ ist am 3. November 1999 in die Schweiz eingereist. Ein von ihm eingereichtes Asylgesuch wurde rechtskräftig abgewiesen. Seit dem 15. Juli 2001 galt er als verschwunden; gemäss eigenen Angaben lebte er in der Folge ohne gültige Aufenthaltsbewilligung in der Schweiz. Am 8. März 2006 stellte er beim Migrationsamt des Kantons Zürich ein Gesuch um Erteilung einer Aufenthaltsbewilligung zum Verbleib bei seinem am 25. Juni 2000 unehelich geborenen Sohn Y._, welcher im Besitz des schweizerischen Bürgerrechts ist. Mit Verfügung vom 15. August 2008 trat das Migrationsamt auf das Gesuch nicht ein. Ein von X._ hiergegen erhobener Rekurs wurde vom Regierungsrat des Kantons Zürich abgewiesen.
B. X._ liess daraufhin beim Verwaltungsgericht des Kantons Zürich Beschwerde erheben. Er beantragte für das verwaltungsgerichtliche Verfahren die unentgeltliche Rechtspflege und die Befreiung von der Kostenvorschusspflicht. In einer prozessleitenden Verfügung vom 26. März 2009 verweigerte der Instruktionsrichter des Verwaltungsgerichts X._ die Gewährung der unentgeltlichen Rechtspflege und forderte ihn auf, einen Gerichtskostenvorschuss von Fr. 2'560.-- zu leisten.
C. Mit Eingabe vom 4. Mai 2009 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Er beantragt im Wesentlichen, die Verfügung des Verwaltungsgerichts aufzuheben und ihn von der Kostenvorschusspflicht im verwaltungsgerichtlichen Verfahren zu befreien.
Auf das Einholen von Vernehmlassungen wurde verzichtet.

Erwägungen:
1. 1.1 Gegenstand des vorinstanzlichen Verfahrens ist ein Zwischenentscheid betreffend die Verweigerung der unentgeltlichen Rechtspflege und betreffend die Verpflichtung zur Leistung eines Kostenvorschusses. Solche Zwischenentscheide können einen nicht wieder gutzumachenden Nachteil bewirken und sind daher gemäss Art. 93 Abs. 1 lit. a BGG gesondert anfechtbar (Urteil 2C_143/2008 vom 10. März 2008 E. 2 mit Hinweisen).
In der Sache selbst geht es um die Verweigerung einer Aufenthaltsbewilligung für den Beschwerdeführer. Gemäss Art. 83 lit. c Ziff. 2 BGG ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts unzulässig gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumen. Nach dem Grundsatz der Einheit des Verfahrens steht zur Anfechtung eines Zwischenentscheides das in der Sache selbst gegebene Rechtsmittel zur Verfügung (<ref-ruling> E. 2.2. S. 647).
Gemäss Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; in Kraft gewesen bis 31. Dezember 2007; hier aber anwendbar gemäss Art. 126 Abs. 1 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer [AuG; SR 142.20]) entscheiden die zuständigen Behörden, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt und Niederlassung. Es besteht damit grundsätzlich kein Anspruch auf Erteilung einer Aufenthaltsbewilligung, es sei denn, der Ausländer oder seine in der Schweiz lebenden Angehörigen könnten sich auf eine Sondernorm des Bundesrechts oder eines Staatsvertrages berufen.
Als mögliche Anspruchsgrundlagen stehen insbesondere Art. 8 EMRK und Art. 13 Abs. 1 BV in Frage. Damit ein ausländischer Staatsangehöriger aufgrund des von diesen Bestimmungen garantierten Schutzes des Familienlebens einen grundsätzlichen Bewilligungsanspruch herleiten kann, bedarf es einer engen und effektiv gelebten Beziehung zu einem Familienangehörigen mit Schweizer Staatsangehörigkeit oder Niederlassungsbewilligung. Eine intakte Beziehung zu einem eigenen Kind, welches das Recht hat, sich in der Schweiz aufzuhalten, reicht für die Bejahung der Beschwerdelegitimation ebenfalls aus, auch wenn dieses Kind familienrechtlich nicht der elterlichen Sorge oder Obhut des ausländischen Staatsangehörigen untersteht (vgl. <ref-ruling> E. 1d mit Hinweisen).
Im vorliegenden Fall hat der Beschwerdeführer mit einer Schweizerin einen gemeinsamen Sohn, welcher ebenfalls das Schweizer Bürgerrecht besitzt. Der Beschwerdeführer ist nicht obhutsberechtigt, hält jedoch mittels eines begleiteten Besuchsrechts den Kontakt zu seinem Sohn aufrecht. Gemäss dem Gesagten steht deshalb die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen. Es bleibt eine Frage der materiellen Beurteilung, ob es unter den konkreten Umständen mit Art. 8 EMRK bzw. Art. 13 BV vereinbar ist, dass die zürcherischen Behörden dem Beschwerdeführer eine Aufenthaltsbewilligung für die Schweiz verweigert haben, bzw. dass das Verwaltungsgericht des Kantons Zürich das vom Beschwerdeführer hiergegen eingelegte Rechtsmittel als aussichtslos bezeichnet hat.
Da die Beschwerde unter Einhaltung der gesetzlichen Frist (Art. 100 Abs. 1 BGG) und Form (Art. 42 BGG) von einer durch die Entscheidung besonders berührten Partei mit einem schutzwürdigen Interesse an deren Aufhebung oder Änderung (Art. 89 Abs. 1 BGG) eingereicht wurde, kann darauf grundsätzlich eingetreten werden (unter Vorbehalt von E. 1.2 und 1.3 hiernach).
1.2 Mit der Beschwerde kann eine Rechtsverletzung nach Art. 95 und 96 BGG geltend gemacht werden. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist daher weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen, und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen. Das Bundesgericht legt sodann seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von Art. 95 BGG (Art. 105 Abs. 2 bzw. Art. 97 Abs. 1 BGG).
1.3 Gemäss Art. 42 Abs. 1 BGG hat die Rechtsschrift die Begehren und deren Begründung zu enthalten. In der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (Art. 42 Abs. 2 BGG). Die Vorbringen müssen sachbezogen sein, damit aus der Beschwerdeschrift ersichtlich ist, in welchen Punkten und weshalb der angefochtene Entscheid beanstandet wird. Dies setzt voraus, dass sich ein Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheides auseinandersetzt (<ref-ruling>). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG; <ref-ruling> E. 1.4.2 S. 254).
2. Der Beschwerdeführer macht geltend, die Vorinstanz habe dadurch, dass sie die materielle Behandlung des Rechtsmittels von der Leistung eines Kostenvorschusses abhängig machte, seinen verfassungsmässigen Anspruch auf unentgeltliche Rechtspflege verletzt. Dieses Verhalten müsse zudem als willkürlich bezeichnet werden.
2.1 Gemäss Art. 29 Abs. 3 BV haben Personen, die nicht über die erforderlichen Mittel verfügen und deren Rechtsbegehren nicht aussichtslos erscheint, Anspruch auf unentgeltliche Rechtspflege. Falls es darüber hinaus zur Wahrung ihrer Rechte notwendig ist, haben sie ausserdem Anspruch auf unentgeltlichen Rechtsbeistand (<ref-ruling> E. 2.2, mit Hinweisen). Der Beschwerdeführer ist unbestrittenermassen bedürftig. Vorliegend zu prüfen ist somit nur die Beurteilung der Aussichtslosigkeit.
2.1.1 Als aussichtslos sind nach der bundesgerichtlichen Rechtsprechung Prozessbegehren anzusehen, bei denen die Gewinnaussichten beträchtlich geringer sind als die Verlustgefahren und die deshalb kaum als ernsthaft bezeichnet werden können. Dagegen gilt ein Begehren nicht als aussichtslos, wenn sich Gewinnaussichten und Verlustgefahren ungefähr die Waage halten oder jene nur wenig geringer sind als diese. Massgebend ist, ob eine Partei, die über die nötigen finanziellen Mittel verfügt, sich bei vernünftiger Überlegung zu einem Prozess entschliessen würde; eine Partei soll einen Prozess, den sie auf eigene Rechnung und Gefahr nicht führen würde, nicht deshalb anstrengen können, weil er sie nichts kostet (<ref-ruling> E. 2.3.1).
2.1.2 Das Verwaltungsgericht hat die bei ihm eingereichte Beschwerde unter Hinweis auf die Begründung des regierungsrätlichen Rekursentscheids als aussichtslos bezeichnet. Der Beschwerdeführer erachtet seine Beschwerde dagegen als aussichtsreich. Er macht im Wesentlichen geltend, dass er aufgrund des Besuchsrechts gegenüber seinem Sohn sowie einer besonders ausgeprägten affektiven Beziehung zu diesem einen Anspruch auf Erteilung einer Aufenthaltsbewilligung habe.
2.1.3 Gemäss der vom Regierungsrat und vom Migrationsamt des Kantons Zürich zutreffend wiedergegebenen bundesgerichtlichen Rechtsprechung verschafft ein Besuchsrecht gegenüber einem in der Schweiz fest anwesenheitsberechtigten Kind dem ausländischen Elternteil im Allgemeinen noch keinen Anspruch auf dauernde Anwesenheit. Unter dem Gesichtspunkt von Art. 8 Ziff. 1 und Ziff. 2 EMRK sowie Art. 13 Abs. 1 BV (vgl. E. 1.1) ist es ausreichend, wenn das Besuchsrecht im Rahmen von Kurzaufenthalten vom Ausland her ausgeübt werden kann, wobei allenfalls die Modalitäten des Besuchsrechts entsprechend auszugestalten sind. Ein weiter gehender Anspruch kann nur dann bestehen, wenn in wirtschaftlicher und affektiver Hinsicht eine besonders enge Beziehung zum Kind besteht, diese Beziehung wegen der Distanz zum Heimatland des Ausländers praktisch nicht aufrecht erhalten werden könnte und das bisherige Verhalten des Ausländers in der Schweiz zu keinerlei Klagen Anlass gegeben hat (sog. tadelloses Verhalten; <ref-ruling> E. 3.c).
2.1.4 Entgegen den Ausführungen des Beschwerdeführers sind solche qualifizierten wirtschaftlichen und affektiven Bindungen zwischen ihm und seinem Sohn nicht ersichtlich: Zwar ist unbestritten, dass er sein begleitetes Besuchsrecht regelmässig ausübt und die eingereichten Verlaufsberichte sich grundsätzlich positiv über die Begegnungen zwischen ihm und seinem Sohn äussern. Inwiefern aber eine affektive Bindung vorliegen soll, deren Intensität über jene einer normalen Vater-Sohn-Beziehung hinausginge, ist nicht ersichtlich und wird letztlich auch vom Beschwerdeführer nicht dargelegt. Auch kann nicht von einer wirtschaftlichen Abhängigkeit des Sohnes vom Beschwerdeführer gesprochen werden, zumal dieser nicht in der Lage ist, Unterhaltsbeiträge zu bezahlen. Ebenso ist festzustellen, dass das Verhalten des Beschwerdeführers wiederholt zu Klagen Anlass gegeben hat: Mit Urteil des Bezirksgerichts Zürich vom 11. September 2002 wurde er der Wiederhandlung gegen das ANAG schuldig gesprochen und zu einer bedingt vollziehbaren Gefängnisstrafe von drei Monaten verurteilt. Mit Urteil vom 17. April 2007 wurde er vom Bezirksgericht Zürich wegen weiterer Vergehen gegen das ANAG sowie wegen des Fälschens von Ausweisen schuldig gesprochen. Der mit Urteil vom 11. September 2002 gewährte bedingte Aufschub der dreimonatigen Gefängnisstrafe wurde widerrufen und der Beschwerdeführer unter Einbezug dieser Sanktion mit einer Geldstrafe von 150 Tagessätzen zu je Fr. 30.-- bestraft.
2.1.5 Aufgrund des Fehlens von qualifizierten wirtschaftlichen und affektiven Bindungen einerseits und seinem deliktischen Verhalten andererseits erscheint als nahezu gewiss, dass dem Beschwerdeführer kein Anspruch auf dauernde Anwesenheit in der Schweiz zwecks Ausübung seines Besuchsrechts zusteht. Dass ihm die Ausübung eines Besuchsrechts von seinem Heimatland aus a priori nicht möglich sein soll, ist nicht ersichtlich und wird auch nicht behauptet.
2.2 Bei dieser Sachlage ist die einstweilige Schlussfolgerung der Vorinstanz, die bei ihr anhängig gemachte Beschwerde erscheine aussichtslos, nicht zu beanstanden. Die Verweigerung der unentgeltlichen Rechtspflege durch die Vorinstanz ist daher zu Recht erfolgt, und die Beschwerde erweist sich in diesem Punkt als unbegründet.
3. Der Beschwerdeführer rügt sodann eine Verletzung des rechtlichen Gehörs (Art. 29 Abs. 2 BV), indem er behauptet, die Vorinstanz sei in der angefochtenen Verfügung nicht auf die von ihm vorgetragenen Argumente bezüglich der Prozessaussichten eingegangen.
3.1 Der Grundsatz des rechtlichen Gehörs als persönlichkeitsbezogenes Mitwirkungsrecht verlangt, dass die Behörde die Vorbringen des Betroffenen auch tatsächlich hört, sorgfältig und ernsthaft prüft und in der Entscheidfindung berücksichtigt. Daraus folgt die grundsätzliche Pflicht der Behörde, ihren Entscheid zu begründen. Der Bürger soll wissen, warum die Behörde entgegen seinem Antrag entschieden hat, weshalb die Begründung des Entscheids so abgefasst sein muss, dass der Betroffene ihn gegebenenfalls sachgerecht anfechten kann. Dies ist nur dann möglich, wenn sowohl er wie auch die Rechtsmittelinstanz sich über die Tragweite des Entscheids ein Bild machen können. In diesem Sinne müssen wenigstens kurz die Überlegungen genannt werden, von denen sich die Behörde leiten liess und auf welche sich ihr Entscheid stützt (<ref-ruling> E. 2.b).
3.2 Die vom Beschwerdeführer erhobene Rüge vermag nicht durchzudringen: Das Verwaltungsgericht hat auf die Erwägungen des regierungsrätlichen Entscheids verwiesen und festgestellt, dass diese durch die vom Beschwerdeführer vorgebrachten Einwendungen nicht entscheidend entkräftet werden. Zwar erscheinen die Ausführungen der Vorinstanz etwas knapp und pauschal. In Anbetracht dessen, dass es sich beim Anfechtungsobjekt nicht um einen vollständigen materiellen Entscheid, sondern um eine verfahrensleitende Verfügung handelt, bei welcher lediglich eine prima facie-Prüfung der Prozesschancen bzw. der materiellen Rechtslage vorzunehmen war, ist darin jedoch keine Gehörsverletzung zu erkennen.
4. Soweit sich der Beschwerdeführer gegen die Höhe des vom Verwaltungsgericht einverlangten Kostenvorschusses beschwert und in diesem Zusammenhang eine Verletzung des Verhältnismässigkeitsprinzips rügt, kann auf die Beschwerde nicht eingetreten werden: Das in Art. 5 Abs. 2 BV als allgemeiner Verfassungsgrundsatz verankerte Verhältnismässigkeitsgebot kann im Rahmen einer Beschwerde in öffentlich-rechtlichen Angelegenheiten bei der Anwendung kantonalen Rechts ausserhalb des Schutzbereichs spezieller Grundrechte nur unter dem Gesichtswinkel des Willkürverbots angerufen werden (<ref-ruling> E. 4). Im vorliegenden Fall richtet sich die Höhe der Gerichtskosten und mithin des einzuverlangenden Kostenvorschusses nach den Bestimmungen des kantonalen Gesetzesrechts. Inwiefern das beanstandete Vorgehen das Willkürverbot oder spezielle Grundrechte der Bundesverfassung verletzen soll, wird nicht dargetan und ist auch nicht ersichtlich.
5. Es ergibt sich aus den genannten Gründen, dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten abzuweisen ist, soweit darauf eingetreten werden kann. Entsprechend diesem Verfahrensausgang sind die Kosten des bundesgerichtlichen Verfahrens dem Beschwerdeführer aufzuerlegen (Art. 65 f. BGG). Dem Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung für das bundesgerichtliche Verfahren kann nicht entsprochen werden, da die eingereichte Beschwerde als aussichtslos zu bezeichnen ist (vgl. Art. 64 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung im bundesgerichtlichen Verfahren wird abgewiesen.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, der Sicherheitsdirektion und dem Regierungsrat des Kantons Zürich, dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 27. Mai 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Zähndler