Sachverhalt:
A. Der türkische Staatsangehörige X._ (geb. 1977) heiratete am 4. September 2001 die in der Schweiz niedergelassene Y._ (geb. 1972) und erhielt in der Folge eine Aufenthaltsbewilligung. Die Eheleute X._-Y._ sind Eltern der Kinder A._ (geb. 2003) und B._ (geb. 2006). Am 20. November 2007 ersuchte X._ das Migrationsamt des Kantons Thurgau um Verlängerung seiner Aufenthaltsbewilligung. Dieses teilte mit Schreiben vom 24. Januar 2008 mit, es prüfe die Anordnung fremdenpolizeilicher Massnahmen (unter anderem Nichtverlängerung der Aufenthaltsbewilligung). Weiter verlangte das Migrationsamt für das anstehende Verfahren einen Kostenvorschuss von Fr. 300.-- und machte darauf aufmerksam, dass im Säumnisfall nicht auf das Gesuch um Verlängerung der Aufenthaltsbewilligung eingetreten werde. Da X._ den verlangten Kostenvorschuss nicht innert der angesetzten Frist bezahlte, trat das Migrationsamt des Kantons Thurgau mit Entscheid vom 5. März 2008 nicht auf sein Gesuch um Verlängerung der am 11. November 2007 abgelaufenen Aufenthaltsbewilligung ein. Das Migrationsamt stellte fest, dass damit die Aufenthaltsbewilligung von X._ abgelaufen sei und dieser wurde aufgefordert, die Schweiz spätestens bis zum 31. Mai 2008 zu verlassen.
Gegen diesen Entscheid des Migrationsamts erhob X._ Rekurs beim Departement für Justiz und Sicherheit des Kantons Thurgau, das ihn in der Folge aufforderte, für das Rekursverfahren einen Kostenvorschuss von Fr. 900.-- zu leisten. Gegen den Kostenvorschussentscheid erhob X._ Beschwerde beim Verwaltungsgericht des Kantons Thurgau, welches jedoch mit Urteil vom 18. Juni 2008 auf die Beschwerde nicht eintrat, da diese verspätet eingereicht worden war. Dieser Entscheid des Verwaltungsgerichts blieb unangefochten. Am 1. Juli 2008 verfügte das Departement für Justiz und Sicherheit, auf den Rekurs von X._ werde nicht eingetreten, da der auferlegte Kostenvorschuss nicht geleistet worden war.
B. Mit Schreiben vom 17., 23. und 30. Oktober 2008 wandte sich X._ an das Migrationsamt des Kantons Thurgau und stellte den Antrag, sein Gesuch um Verlängerung der Aufenthaltsbewilligung sei materiell zu prüfen. Das Migrationsamt teilte mit Schreiben vom 5. November 2008 mit, das ausländerrechtliche Verfahren gegen X._ sei "seit längerer Zeit rechtskräftig abgeschlossen" und auf das Begehren um materielle Beurteilung des Gesuchs werde nicht eingetreten. Am 27. November 2008 gelangte X._ mit einer Aufsichtsbeschwerde an das Departement für Justiz und Sicherheit und beantragte, das Migrationsamt sei anzuweisen, sein Gesuch um Verlängerung der Aufenthaltsbewilligung materiell zu beurteilen und eine entsprechende rechtsfähige Verfügung zu erlassen. Das Departement trat mit Entscheid vom 9. Januar 2009 mit der Begründung, es handle sich hier um eine "res iudicata", auf die Aufsichtsbeschwerde nicht ein. Eine dagegen erhobene Beschwerde an das Verwaltungsgericht des Kantons Thurgau blieb erfolglos; dieses wies die Beschwerde mit Urteil vom 8. April 2009 ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 29. Mai 2009 beantragt X._ dem Bundesgericht, der Entscheid des Verwaltungsgerichts des Kantons Thurgau sei aufzuheben und das Verwaltungsgericht sei anzuweisen, die Beschwerde neu zu beurteilen, bzw. das Migrationsamt sei anzuweisen, die Aufenthaltsbewilligung zu verlängern. Gerügt wird ein Verstoss gegen das Willkürverbot sowie sinngemäss eine Rechtsverweigerung durch die Vorinstanzen. Sodann ersucht X._ um die Gewährung der unentgeltlichen Rechtspflege.
D. Das Verwaltungsgericht, das Departement für Justiz und Sicherheit und das Migrationsamt des Kantons Thurgau sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.
Am 5. Juni 2009 erkannte der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss aufschiebende Wirkung zu.

Erwägungen:
1. 1.1 Gemäss <ref-law> ist die Beschwerde in öffentlichrechtlichen 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äumt.
1.2 Am 1. Januar 2008 ist das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) in Kraft getreten. Art. 126 Abs. 1 AuG bestimmt, dass auf Gesuche, die vor dem Inkrafttreten dieses Gesetzes eingereicht worden sind, das bisherige Recht anwendbar bleibt. Zwar wurde das ursprüngliche Gesuch um Verlängerung der Aufenthaltsbewilligung vor Inkrafttreten des Ausländergesetzes gestellt; Streitgegenstand bildet hier aber die Frage, ob das Migrationsamt auf die im Oktober 2008 gestellten Gesuche zu Recht nicht eingetreten ist (vgl. dazu E. 3.3). Daraus ergibt sich, dass diese Gesuche nach dem neuen Recht zu beurteilen sind.
1.3 Gemäss Art. 43 Abs. 1 AuG hat der ausländische Ehegatte einer Person mit Niederlassungsbewilligung Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, solange die Ehegatten zusammen wohnen.
Als Ehegatte einer niedergelassenen Ausländerin steht dem Beschwerdeführer gestützt auf die erwähnte Bestimmung im Grundsatz ein Anspruch auf Verlängerung der Aufenthaltsbewilligung zu. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen den auf kantonales Recht gestützten Nichteintretensentscheid des Verwaltungsgerichts erweist sich damit als zulässig (<ref-law>), und der Beschwerdeführer ist als direkter Adressat und Betroffener des angefochtenen Entscheids hierzu legitimiert (<ref-law>).
1.4 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann insbesondere geltend gemacht werden, der angefochtene Entscheid verletze Bundesrecht - inklusive Bundesverfassungsrecht -, Völkerrecht sowie kantonale verfassungsmässige Rechte (<ref-law>). 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 (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (<ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels sich für den Ausgang des Verfahrens als entscheidend erweist (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
1.5 Nicht einzutreten ist auf den Antrag, das Migrationsamt sei anzuweisen, die Aufenthaltsbewilligung zu verlängern. Streitgegenstand ist bloss, ob dem Beschwerdeführer ein Anspruch auf Beurteilung seines Verlängerungsgesuchs zusteht; in Frage kommen kann allenfalls - je nach Ausgang des Verfahrens - nur eine Rückweisung der Sache an das Migrationsamt zur materiellen Prüfung.
2. 2.1 Das Verwaltungsgericht des Kantons Thurgau stützt seinen Entscheid im Wesentlichen auf § 71 des Gesetzes [des Kantons Thurgau] vom 23. Februar 1981 über die Verwaltungsrechtspflege (VRG/TG; RB 170.1). Gemäss dessen Absatz 1 kann bei ungerechtfertigter Verweigerung oder Verzögerung einer vorgeschriebenen Amtshandlung, Missbrauch der Amtsgewalt oder willkürlicher Ausübung von Befugnissen eine Aufsichtsbeschwerde erhoben werden.
Die Vorinstanz führte aus, das Anwesenheitsrecht des Beschwerdeführers sei mit dem Ablauf der Aufenthaltsbewilligung erloschen. Der Beschwerdeführer habe aus eigenem Verschulden zwei beziehungsweise sogar drei Fristen, welche ihm eine materielle Prüfung seines Verlängerungsgesuchs ermöglicht hätten, ungenutzt verstreichen lassen. Der Beschwerdeführer habe es sich somit offensichtlich selber zuzuschreiben, wenn die Prüfung seines grundsätzlich vorhandenen Rechtsanspruchs verhindert worden sei. Die vom Beschwerdeführer geltend gemachten neuen Tatsachen (neue Arbeitsstelle für ihn und seine Ehefrau) hätten nur im erstinstanzlichen Verfahren vor dem Migrationsamt oder im allenfalls darauf folgenden Rekursverfahren geltend gemacht werden können; dies habe sich der Beschwerdeführer durch das Verpassen der Fristen selber verbaut.
2.2 Der Beschwerdeführer macht geltend, das Verwaltungsgericht habe im angefochtenen Entscheid seine persönlichen Verhältnisse gar nicht in Erwägung gezogen und einen willkürlichen Entscheid gefällt. Das Migrationsamt habe auf diverse Gesuche und Schreiben des Beschwerdeführers betreffend neuer Arbeitsstelle und gesundheitlicher Probleme überhaupt nicht reagiert. Damit rügt der Beschwerdeführer (sinngemäss) eine Rechtsverweigerung durch das Migrationsamt.
3. 3.1 Eine formelle Rechtsverweigerung liegt nach der Praxis des Bundesgerichts vor, wenn eine Behörde auf eine ihr frist- und formgerecht unterbreitete Sache nicht eintritt, obschon sie darüber befinden müsste. Überspitzter Formalismus als besondere Form der Rechtsverweigerung ist gegeben, wenn für ein Verfahren rigorose Formvorschriften aufgestellt werden, ohne dass die Strenge sachlich gerechtfertigt wäre, wenn die Behörde formelle Vorschriften mit übertriebener Schärfe handhabt oder an Rechtsschriften überspannte Anforderungen stellt und damit dem Bürger den Rechtsweg in unzulässiger Weise versperrt. Ob eine solche Rechtsverweigerung vorliegt, prüft das Bundesgericht frei. Die Auslegung und Anwendung des einschlägigen kantonalen Rechts untersucht es hingegen nur unter dem Gesichtswinkel der Willkür (<ref-ruling> E. 2.1 S. 9 mit Hinweisen).
3.2 Zwar ist der Vorinstanz zuzustimmen, wenn sie ausführt, die erfolglos angefochtene Nichteintretensverfügung des Migrationsamts des Kantons Thurgau vom 5. März 2008 sei in Rechtskraft erwachsen. Allerdings ging diesem Entscheid keine materielle Prüfung des Gesuchs des Beschwerdeführers um Verlängerung seiner Aufenthaltsbewilligung - auf welche er grundsätzlich Anspruch hätte (vgl. E. 1.3 hiervor) - voraus; das Migrationsamt trat mangels Bezahlung des Kostenvorschusses (materiell) gar nicht auf das Gesuch ein.
Der Beschwerdeführer wandte sich im Oktober 2008 - nach Eintritt der Rechtskraft der Verfügung vom 5. März 2008 - insgesamt dreimal an das Migrationsamt und beantragte, sein Gesuch um Verlängerung sei materiell zu prüfen. Das Migrationsamt vertrat die Auffassung, das ausländerrechtliche Verfahren sei "seit längerer Zeit rechtskräftig abgeschlossen" und trat auf die Gesuche nicht ein. Das Departement für Justiz und Sicherheit sowie das Verwaltungsgericht schützten diese Entscheide mit dem Hinweis, es handle sich um eine "res iudicata" und der Beschwerdeführer habe aus eigenem Verschulden (Verpassen der Frist) eine materielle Prüfung seines Gesuchs vereitelt.
3.3 Die Vorinstanzen übersehen in ihrer Argumentation jedoch, dass bis jetzt noch gar kein materieller Entscheid über das Gesuch um Verlängerung der Aufenthaltsbewilligung ergangen ist, weil das Ende November 2007 angehobene Verfahren mit einem formellen Nichteintretensentscheid abgeschlossen wurde. Zwar hat es der Beschwerdeführer durchaus selber zu verantworten, dass in Bezug auf sein Gesuch vom 20. November 2007 kein Entscheid in der Sache gefällt werden konnte, da er die ihm obliegenden Verfahrenshandlungen nicht fristgerecht vornahm. Den Anspruch auf einen Entscheid in der Sache hat der Beschwerdeführer damit aber nicht verwirkt. Er kann und konnte ein neues Gesuch um Verlängerung seiner Aufenthaltsbewilligung einreichen, was er mit Datum vom 17., 23. und 30. Oktober 2008 auch getan hat. Das Migrationsamt hätte zwar wiederum einen Kostenvorschuss verlangen können; hingegen war es nicht zulässig, auf die erneut gestellten Gesuche einfach nicht einzutreten. In Rechtskraft erwachsen bzw. "res iudicata" war nur der Entscheid, das im November 2007 angehobene Verfahren nicht weiterzuführen. Auf ein neues Gesuch um Prüfung des grundsätzlich nach wie vor bestehenden Aufenthaltsanspruchs kann sich die Rechtskraft nicht beziehen. Das Handeln des Migrationsamtes stellt eine formelle Rechtsverweigerung dar, womit die Vorinstanz auf die Rechtsverweigerungsbeschwerde des Beschwerdeführers hätte eintreten und diese gutheissen müssen (vgl. Urteil 2C_244/2007 vom 10. Oktober 2007 E. 4.1).
Anders würde es sich nur dann verhalten, wenn das Vorgehen des Beschwerdeführers als rechtsmissbräuchlich bezeichnet werden müsste. Solches Verhalten ist hier aber nicht ersichtlich: vielmehr scheinen finanzielle Schwierigkeiten sowie Verständigungsprobleme der Grund für die Versäumnisse des Beschwerdeführers gewesen zu sein.
3.4 Dem von der Vorinstanz angeführten Urteil 2C_297/2007 vom 6. August 2007 lag ein anderer Sachverhalt zu Grunde: In diesem Verfahren hatten das kantonale Amt und das Departement in der Sache entschieden und das Verwaltungsgericht trat in der Folge wegen verspäteter Leistung des Kostenvorschusses nicht auf die Beschwerde ein, womit der erfolglos angefochtene Sachentscheid in Rechtskraft erwuchs. Im vorliegenden Fall erging aber (noch) gar kein Entscheid in der Sache; die Vorinstanz geht somit fehl, wenn sie von einer "res iudicata" in materieller Hinsicht ausgeht. Wird - wie hier - auf eine Rechtsvorkehr nicht eingetreten, ohne dass der ins Recht gelegte Anspruch materiell beurteilt wurde, so erwächst der Nichteintretensentscheid - wie erwähnt - nur mit Wirkung auf das angehobene Verfahren in Rechtskraft. Die Rechtskraft bezieht sich aber nicht auf den materiellen Rechtsanspruch; dieser kann mit einem neuen Gesuch erneut geltend gemacht werden.
4. 4.1 Zusammengefasst ergibt sich, dass die Vorinstanz die Rechtsverweigerungsbeschwerde hätte gutheissen müssen, da das kantonale Migrationsamt eine formelle Rechtsverweigerung begangen hat. Die vorliegende Beschwerde erweist sich somit als begründet und ist gutzuheissen, soweit darauf eingetreten werden kann. Der Entscheid des Verwaltungsgerichts vom 8. April 2009 ist aufzuheben und die Sache an das Migrationsamt des Kantons Thurgau zur materiellen Beurteilung (Prüfung des Gesuchs um Verlängerung der Aufenthaltsbewilligung) zurückzuweisen.
4.2 Bei diesem Ausgang des Verfahrens sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Eine Parteientschädigung ist nicht geschuldet (<ref-law>). Das Gesuch um Gewährung der unentgeltlichen Rechtspflege wird damit gegenstandslos. Über die Kosten- und Entschädigungsfolgen im vorinstanzlichen Verfahren hat das Verwaltungsgericht neu zu entscheiden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird gutgeheissen, soweit darauf einzutreten ist, und das Urteil des Verwaltungsgerichts des Kantons Thurgau vom 8. April 2009 wird aufgehoben.
2. Die Angelegenheit wird zur materiellen Prüfung an das Migrationsamt des Kantons Thurgau sowie zu neuem Entscheid über die Kosten- und Entschädigungsfolgen im vorinstanzlichen Verfahren an das Verwaltungsgericht des Kantons Thurgau zurückgewiesen.
3. Es werden keine Kosten erhoben.
4. Das Gesuch um unentgeltliche Rechtspflege wird als gegenstandslos abgeschrieben.
5. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Thurgau und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 21. Dezember 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Winiger