Sachverhalt:
A. Der 1982 geborene türkische Staatsangehörige X._ reiste am 10. Juli 2002 in die Schweiz ein und stellte hier ein Asylgesuch, welches jedoch abgelehnt wurde. Gegen den abschlägigen Entscheid führte er Beschwerde bei der damaligen Asylrekurskommission (ARK). Noch während des hängigen Beschwerdeverfahrens heiratete er am 28. November 2003 seine Landsfrau Y._, welche den Status eines anerkannten Flüchtlings hatte und über die Niederlassungsbewilligung verfügte. Daraufhin wurde X._ eine Jahresaufenthaltsbewilligung ausgestellt. Im April 2006 wurde die gemeinsame Tochter Z._ geboren, welche wie ihre Mutter die Niederlassungsbewilligung erhielt. Bereits im Mai 2006 kam es zur Trennung der Eheleute, worauf das Amt für Polizeiwesen und Zivilrecht des Kantons Graubünden mit Verfügung vom 1. Juni 2007 die Verlängerung der Aufenthaltsbewilligung von X._ verweigerte. Eine hiergegen erhobene Beschwerde beim Departement für Justiz, Sicherheit und Gesundheit des Kantons Graubünden blieb ohne Erfolg.
B. X._ liess daraufhin beim Verwaltungsgericht des Kantons Graubünden Beschwerde erheben. In seinem Entscheid vom 15. April 2008 wies dieses die Beschwerde ab.
C. Mit Eingabe vom 15. September 2008 reichte X._ eine als "Verfassungsbeschwerde" bezeichnete Rechtsschrift ein. Darin wurde im Wesentlichen beantragt, das Urteil des Verwaltungsgerichts sei aufzuheben und das Amt für Polizeiwesen und Zivilrecht des Kantons Graubünden sei anzuweisen, die Aufenthaltsbewilligung des Beschwerdeführers zu verlängern.
Während das Amt für Polizeiwesen und Zivilrecht auf eine Vernehmlassung verzichtet, schliesst das Departement für Justiz, Sicherheit und Gesundheit auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Graubünden beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werde.
Mit Verfügung vom 2. Oktober 2008 erteilte der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde die aufschiebende Wirkung.

Erwägungen:
1. 1.1 Das Bundesgericht prüft seine Zuständigkeit und die Zulässigkeit eines Rechtsmittels von Amtes wegen (<ref-law>; <ref-ruling>).
Gemäss <ref-law> 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. 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; anwendbar gem. 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.
Der Beschwerdeführer beruft sich auf Art. 8 EMRK und <ref-law>. 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 eine gemeinsame Tochter mit einer niedergelassenen Ausländerin. Infolge der Aufhebung des gemeinsamen Haushalts wurde vereinbart, dass die Obhut über das Kind der Mutter zukommen soll. Der Beschwerdeführer hält jedoch mittels eines begleiteten Besuchsrechts den Kontakt zu seiner Tochter aufrecht. Gemäss dem Gesagten steht deshalb die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen. Ob die Nichtverlängerung der Aufenthaltsbewilligung unter den konkreten Umständen mit Art. 8 EMRK bzw. <ref-law> vereinbar ist, bleibt dagegen Frage der materiellen Beurteilung.
Die Verfassungsbeschwerde ist im Verhältnis zur Beschwerde in öffentlich-rechtlichen Angelegenheiten subsidiär (<ref-law>). Da hier die Letztere zur Verfügung steht, ist das Rechtsmittel als Beschwerde in öffentlich-rechtlichen Angelegenheiten entgegen zu nehmen. Die falsche Bezeichnung der Beschwerdeschrift schadet dem Beschwerdeführer nicht, sofern bezüglich des statthaften Rechtsmittels sämtliche Prozessvoraussetzungen erfüllt sind (<ref-ruling> E. 1.2 mit Hinweisen).
1.2 Die Beschwerde wurde unter Einhaltung der gesetzlichen Frist (<ref-law>) und Form (<ref-law>) von einer durch die Entscheidung besonders berührten Partei mit einem schutzwürdigen Interesse an deren Aufhebung oder Änderung (<ref-law>) eingereicht. Sie richtet sich gegen einen letztinstanzlichen kantonalen Endentscheid (<ref-law> und <ref-law>) in einer Angelegenheit des öffentlichen Rechts (<ref-law>). Auf die Beschwerde kann daher grundsätzlich eingetreten werden (vgl. jedoch E. 1.4).
1.3 Mit der Beschwerde kann eine Rechtsverletzung nach Art. 95 und 96 BGG geltend gemacht werden. 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; 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 (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 105 Abs. 2 bzw. <ref-law>).
1.4 Gemäss <ref-law> hat die Rechtsschrift die Begehren und deren Begründung zu enthalten; im Rahmen der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). 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 der 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 (<ref-law>; <ref-ruling> E. 1.4.2 S. 254). Diesen Begründungsanforderungen vermag die vorliegende Beschwerde insoweit nicht zu genügen, als pauschal "die Verletzung von Bundesrecht inklusive die Überschreitung des Ermessens gemäss <ref-law>" gerügt wird, ohne dass dies näher substantiiert wird. In diesem Umfang kann auf die Beschwerde daher nicht eingetreten werden.
2. 2.1 Der Beschwerdeführer macht im Wesentlichen geltend, dass er aufgrund der Beziehung zu seiner Tochter gestützt auf Art. 8 Ziff. 1 EMRK bzw. <ref-law> einen Anspruch auf Verlängerung der Aufenthaltsbewilligung habe.
2.2 Der in Art. 8 Ziff. 1 EMRK und <ref-law> garantierte Anspruch auf Achtung des Familienlebens 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 und zur Verhinderung von strafbaren Handlungen, zum Schutze 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 öffentlichen Interessen an der Verweigerung, wobei letztere in dem Sinne überwiegen müssen, dass sich der Eingriff als notwendig erweist (<ref-ruling> E. 2 S. 6, mit Hinweisen). Auch in den durch <ref-law> geschützten Bereich kann unter den in <ref-law> genannten Voraussetzungen eingegriffen werden.
2.3 Der nicht obhutsberechtigte Ausländer kann die familiäre Beziehung zu seinen Kindern von Vornherein nur in einem beschränkten Rahmen, nämlich durch Ausübung des ihm eingeräumten Besuchsrechts leben. Hierzu ist es grundsätzlich nicht unabdingbar, dass er dauernd im gleichen Land wie das Kind lebt und dort über eine Aufenthaltsbewilligung verfügt. Wie die Vorinstanz zutreffend ausgeführt hat, 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 und <ref-law> 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.4 Entgegen den Ausführungen des Beschwerdeführers sind solche qualifizierte wirtschaftliche und affektive Bindungen zwischen ihm und seiner Tochter nicht ersichtlich: Zwar ist unbestritten, dass er sein begleitetes Besuchsrecht regelmässig ausübt und die aktenkundigen Verlaufsberichte sich positiv über die Begegnungen zwischen ihm und seiner Tochter äussern. Inwiefern aber eine affektive Bindung vorliegen soll, deren Intensität über jene einer normalen Vater-Tochter-Beziehung hinausginge, ist nicht ersichtlich und wird letztlich auch vom Beschwerdeführer nicht dargelegt. Auch kann nicht von einer wirtschaftlichen Abhängigkeit der Tochter vom Beschwerdeführer gesprochen werden: Dieser bezahlt zwar entsprechend seinen wirtschaftlichen Möglichkeiten Unterhaltsbeiträge für seine Tochter und die Kindsmutter, doch genügen diese nicht, um deren Existenzminimum zu decken: Als Folge der finanziellen Mangellage muss die Kindsmutter gemäss den verbindlichen Feststellungen der Vorinstanz einerseits einer Teilzeitarbeit nachgehen und andererseits finanzielle Unterstützung durch die öffentliche Hand in Anspruch nehmen, um den Unterhalt der Familie sicherzustellen.
2.5 Aufgrund der genannten, nicht über den Rahmen des Üblichen hinausgehenden Umstände ergibt sich, 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. Zwar leuchtet ein, dass die Distanz und die möglicherweise geringeren Verdienstmöglichkeiten in der Türkei die Ausübung des Besuchsrechts erschweren. Bei entsprechender Anpassung der Besuchsmodalitäten (z.B. Ferienaufenthalte) erscheint die Aufrechterhaltung des persönlichen Kontaktes aber realisierbar.
2.6 Nach dem Gesagten ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten abzuweisen, soweit darauf einzutreten ist.
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 Beschwerde als von vornherein aussichtslos zu bezeichnen ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird als Beschwerde in öffentlich-rechtlichen Angelegenheiten entgegen genommen und abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege im bundesgerichtlichen Verfahren wird abgewiesen.
Die Gerichtskosten von Fr. 1'200.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Amt für Polizeiwesen und Zivilrecht Graubünden, dem Departement für Justiz, Sicherheit und Gesundheit Graubünden, dem Verwaltungsgericht des Kantons Graubünden sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 16. Februar 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Zähndler