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.