Sachverhalt:
A. X._ (geb. 1958) ist kroatischer und australischer Staatsangehöriger. 1990 heiratete er in Kroatien die 1964 geborene Landsfrau Y._. Nach der Heirat wanderten die Eheleute nach Australien aus. Aus der Ehe gingen die Kinder A._ (geb. 1995) und B._ (geb. 1998) hervor. Alle Familienmitglieder sind australische Staatsangehörige.
Die Familie X._ und Y._ reiste am 9. März 2001 in die Schweiz ein, wo die Ehefrau eine Anstellung als IT-Beraterin bei einer Schweizer Grossbank antrat und in der Folge eine Aufenthaltsbewilligung erhielt. Der Ehemann, welcher als ausgebildeter Ingenieur den Haushalt besorgte, und die Kinder erhielten Aufenthaltsbewilligungen zum Verbleib bei der Ehefrau bzw. der Mutter.
Seit dem 7. Februar 2004 leben die Eheleute getrennt. Die Kinder wohnen bei der Mutter in Zumikon/ZH. Der Vater, der seit dem 1. Juli 2004 Sozialhilfe bezieht, lebt in der gleichen Gemeinde. Das von der Ehefrau eingeleitete Scheidungsverfahren ist noch nicht rechtskräftig abgeschlossen.
B. Mit Verfügung vom 17. Januar 2005 lehnte die Sicherheitsdirektion des Kantons Zürich das Gesuch von X._ um eine Verlängerung der Aufenthaltsbewilligung ab und setzte ihm eine Ausreisefrist bis 31. Oktober 2005. Ein am 22. September 2005 dagegen erhobener Rekurs beim Regierungsrat des Kantons Zürich blieb erfolglos. Der Regierungsrat stellte mit Entscheid vom 21. Mai 2008 fest, dass X._ keine derart enge Beziehung zu seinen Kindern unterhalte, dass daraus ein Anspruch auf eine Aufenthaltsbewilligung entstehe. Zudem könne sein Verhalten nur beschränkt als weitgehend tadellos bezeichnet werden und es bestehe ein Fürsorgerisiko.
Während des laufenden Rekursverfahrens vor dem Regierungsrat wurde der Ehefrau und den beiden Kindern am 6. November 2006 die Niederlassungsbewilligung erteilt.
Das Verwaltungsgericht des Kantons Zürich wies mit Urteil vom 22. Oktober 2008 die gegen den regierungsrätlichen Entscheid erhobene Beschwerde ab.
C. Mit Eingabe vom 3. Dezember 2008 erhebt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Er beantragt, der vorinstanzliche Entscheid sei aufzuheben und die Sicherheitsdirektion des Kantons Zürich sei anzuweisen, das Gesuch des Beschwerdeführers um Verlängerung der Aufenthaltsbewilligung gutzuheissen. Gerügt wird eine Verletzung von Art. 8 EMRK resp. <ref-law> (Recht auf Familienleben).
D. Das Verwaltungsgericht und der Regierungsrat des Kantons Zürich sowie das Bundesamt für Migration beantragen die Abweisung der Beschwerde.

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 Das streitige Gesuch um Verlängerung der Aufenthaltsbewilligung wurde vor Inkrafttreten des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) am 1. Januar 2008 eingereicht und beurteilt sich daher noch nach dem inzwischen aufgehobenen Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) und seinen Ausführungserlassen (Art. 126 Abs. 1 AuG).
1.3 Da der Beschwerdeführer getrennt von seiner Ehefrau lebt, hat er keinen Bewilligungsanspruch gestützt auf Art. 17 Abs. 2 ANAG. Hingegen verfügen die beiden Kinder des Beschwerdeführers über ein gefestigtes Anwesenheitsrecht in der Schweiz. Zu diesen hat der Beschwerdeführer eine Beziehung, welche intakt scheint und im Rahmen der Möglichkeiten auch gelebt wird. Da er eine familiäre Beziehung zu seinen Kindern pflegt, hat er gestützt auf Art. 8 EMRK einen (bedingten) Rechtsanspruch auf eine Aufenthaltsbewilligung (<ref-ruling> E. 1e S. 5 mit Hinweisen).
Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist demzufolge einzutreten. Ob die Bewilligung verweigert werden durfte, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (vgl. <ref-ruling> E. 1.1.5 S. 150 mit Hinweisen).
1.4 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist daher weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Immerhin prüft das Bundesgericht, 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 u.a. hinsichtlich der Verletzung von Grundrechten. 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 mit Hinweisen).
1.5 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 97 Abs. 1 bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und <ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. 2.1 Art. 8 EMRK - sowie seit dem 1. Januar 2000 auch <ref-law> (vgl. <ref-ruling> E. 7 S. 394) - gewährleisten das Recht auf Achtung des Privat- und Familienlebens. Hat ein Ausländer nahe Verwandte mit einem gefestigten Anwesenheitsrecht in der Schweiz und wird die intakte familiäre Beziehung zu diesen tatsächlich gelebt, kann es die entsprechenden Garantien verletzen, wenn ihm der Verbleib in der Schweiz untersagt und damit das Familienleben vereitelt wird (<ref-ruling> E. 3.1 S. 285 mit Hinweisen). Der Beschwerdeführer beruft sich in diesem Zusammenhang auf seine familiären Bindungen zu seinem Sohn A._ und seiner Tochter B._.
2.2 Zunächst ist festzuhalten, dass der nicht sorgeberechtigte Ausländer die familiäre Beziehung zu seinen Kindern zum Vornherein nur in einem beschränkten Rahmen, nämlich durch Ausübung des ihm eingeräumten Besuchsrechts, leben kann; dazu ist regelmässig nicht erforderlich, dass er sich dauernd im gleichen Land aufhält wie die Kinder. Es ist daher im Allgemeinen zulässig, dem Ausländer, der gegenüber seinen in der Schweiz anwesenheitsberechtigten Kindern bloss über ein Besuchsrecht verfügt, die Aufenthaltsbewilligung zu verweigern. Den Anforderungen von Art. 8 EMRK ist Genüge getan, wenn er das Besuchsrecht im Rahmen von Kurzaufenthalten vom Ausland her ausüben kann, wobei allenfalls dessen Modalitäten geeignet aus- bzw. umzugestalten sind. Die Aufenthaltsbewilligung ist nach der bundesgerichtlichen Rechtsprechung nur dann zu erteilen oder zu erneuern, wenn in wirtschaftlicher und affektiver Hinsicht eine besonders enge Beziehung zum Kind besteht, diese wegen der Distanz zum Heimatland des Ausländers praktisch nicht mehr aufrechterhalten werden könnte und das bisherige Verhalten des Betroffenen in der Schweiz zu keinerlei Klagen Anlass gegeben hat ("tadelloses Verhalten", "comportement irréprochable", "comportamento irreprensibile"; <ref-ruling> E. 3c S. 5, 22 E. 4; Urteil 2A.110/2007 vom 2. August 2007 E. 3.4 mit Hinweisen).
2.2.1 Was das Erfordernis der besonderen Intensität der affektiven Beziehung betrifft, ist dieses regelmässig bloss dann als erfüllt zu erachten, wenn ein grosszügig ausgestaltetes Besuchsrecht eingeräumt ist und dieses kontinuierlich, spontan und reibungslos ausgeübt wird (vgl. Urteile 2A.110/2007 vom 2. August 2007 E. 3.4; 2A.77/2006 vom 15. Februar 2006, E. 2.2.1; 2A.412/1998 vom 15. Dezember 1998, E. 3a).
Diese Voraussetzungen sind vorliegend nicht erfüllt: Der Beschwerdeführer versucht zwar, die Beziehung zu seinen Kindern möglichst normal zu gestalten. Von einer besonders engen Beziehung kann aber gemäss den für das Bundesgericht verbindlichen Feststellungen der Vorinstanz keine Rede sein. Es mag wohl zutreffen, dass der Beschwerdeführer früher, als er die Rolle des Hausmanns innehatte (2001 bis 2004), die Hauptbezugsperson der beiden Kinder war. Dies ist jedoch seit geraumer Zeit nicht mehr der Fall: Das Besuchsrecht ist heute beschränkt auf einen Sonntag im Monat und findet zudem unter Aufsicht einer Begleitperson statt. Das Verwaltungsgericht hat weiter festgestellt, dass sich auch aus den im vorinstanzlichen Verfahren vom Beschwerdeführer eingereichten Anhörungsprotokollen keine besonders enge affektive Beziehung des Beschwerdeführers zu seinen Kindern entnehmen lasse. Dem Beschwerdeführer gelingt es nicht darzulegen, inwiefern diese Schlussfolgerung bundesrechtswidrig sein soll. Auf jeden Fall liegt kein grosszügig ausgestaltetes und regelmässig durchgeführtes Besuchsrecht zwischen dem Beschwerdeführer und seinen Kindern vor. Daran vermögen auch die "faktischen" Begegnungen mit den Kindern auf der Strasse - welche offenbar von diesen nicht vorbehaltlos unterstützt werden - nichts zu ändern.
2.2.2 Auch in wirtschaftlicher Hinsicht besteht im Übrigen keine besonders enge Beziehung des Beschwerdeführers zu seinen Kindern. Die Vorinstanz hat jedoch zu Recht ausgeführt, dass diesem Umstand keine entscheidende Bedeutung zukomme. Es kann damit offen gelassen werden, ob die vom Beschwerdeführer in der Vergangenheit geleistete Kinderbetreuung und Hausarbeit die fehlende wirtschaftliche Unterstützung aufwiegen kann.
2.2.3 Zu berücksichtigen ist jedoch, dass das Verhalten des Beschwerdeführers nicht erlaubt, ihm ein tadelloses Verhalten zu attestieren. Der Beschwerdeführer wurde wegen einer Tätlichkeit gegenüber seiner Ehefrau schuldig gesprochen und mit fünf Tagen Haft bestraft. Zudem wird der Beschwerdeführer seit dem 1. Juni 2004 von der Sozialhilfe unterstützt. Trotz einer Aufenthaltsdauer von über acht Jahren hat er sich in beruflicher Hinsicht in keiner Weise integriert, obwohl ihm dazu genügend Zeit zur Verfügung gestanden wäre und er über eine Ausbildung als Ingenieur verfügt. Aufgrund der bisherigen tatsächlichen Abläufe gibt es keine konkreten Anzeichen dafür, dass seine Sozialhilfeabhängigkeit in absehbarer Zeit dahinfallen könnte. Die allenfalls in Zukunft aus dem Scheidungsurteil anfallenden Unterhaltsbeiträge durch die Ehefrau werden kaum ausreichen, um den gesamten Lebensunterhalt des Beschwerdeführers abzudecken.
2.2.4 Das Verwaltungsgericht ging davon aus, dass die Wahrnehmung des Besuchsrechts mit zumutbarem Aufwand auch von Kroatien aus möglich sei. Der Beschwerdeführer macht diesbezüglich geltend, eine künftige Wohnsitznahme in Kroatien sei für ihn unzumutbar, da die Wirtschaftslage dort für ihn sämtliche beruflichen Perspektiven ausschliesse; nur in Australien bestehe eine realistische Chance auf soziale und arbeitsmarktliche Reintegration. Damit verkennt der Beschwerdeführer zunächst, dass er als kroatisch-australischer Doppelbürger nicht darauf beharren kann, in das Land (Australien) zurückzukehren, von welchem aus das Besuchsrecht praktisch verunmöglicht würde. Eine Rückkehr nach Kroatien erscheint dagegen zumutbar, hat doch der Beschwerdeführer dieses Land erst als 32-jähriger Erwachsener verlassen. Es ist nicht ersichtlich, inwiefern er in Australien besser integriert sein soll als in seiner alten Heimat Kroatien. Die Wahrnehmung des Besuchsrechts ist dem Beschwerdeführer demnach möglich, indem er Wohnsitz in Kroatien nimmt.
3. Daraus ergibt sich, dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten abzuweisen ist.
Dem Verfahrensausgang entsprechend sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Eine Parteientschädigung ist nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Verwaltungsgericht, 2. Kammer, dem Regierungsrat und der Sicherheitsdirektion des Kantons Zürich sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 26. Mai 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Winiger