Sachverhalt:
A. Das Bezirksgericht Steckborn erklärte X._ mit Urteil vom 7. Februar/2. April 2008 des gewerbsmässigen Betrugs schuldig und verurteilte ihn zu 720 Stunden gemeinnütziger Arbeit, unter Anrechnung von 8 Tagen Untersuchungshaft, als Zusatzstrafe zum Urteil des Obergerichts des Kantons Thurgau vom 31. August 2006 und als teilweise Zusatzstrafe zum Urteil des Obergerichts vom 24. August 2004.
B. Das gegen dieses Urteil angerufene Obergericht des Kantons Thurgau wies die gegen den unbedingten Vollzug erfolgte Berufung am 16. Oktober 2008 als unbegründet ab und bestätigte das erstinstanzliche Urteil.
C. X._ führt Beschwerde beim Bundesgericht, in welcher er beantragt, der angefochtene Entscheid sei aufzuheben, und es sei ihm der bedingte Strafvollzug zu gewähren resp. die gemeinnützige Arbeit sei zur Bewährung auszusetzen. Ausserdem beantragt er die Bestellung eines unentgeltlichen Rechtsbeistandes sowie die Gewährung der unentgeltlichen Rechtspflege und Prozessführung.
D. Vernehmlassungen wurden nicht eingeholt.

Erwägungen:
1. 1.1 Das Gericht schiebt gemäss <ref-law> den Vollzug einer Geldstrafe, von gemeinnütziger Arbeit oder einer Freiheitsstrafe von mindestens sechs Monaten und höchstens zwei Jahren in der Regel auf, wenn eine unbedingte Strafe nicht notwendig erscheint, um den Täter von der Begehung weiterer Verbrechen oder Vergehen abzuhalten. Wurde der Täter gemäss Abs. 2 innerhalb der letzten fünf Jahre vor der Tat zu einer bedingten oder unbedingten Freiheitsstrafe von mindestens sechs Monaten oder zu einer Geldstrafe von mindestens 180 Tagessätzen verurteilt, so ist der Aufschub nur zulässig, wenn besonders günstige Umstände vorliegen.
1.2 Die Vorinstanz bejahte die Anwendung des sogenannten Rückfalltatbestandes von <ref-law> auf den vorliegenden Fall, weil der Beschwerdeführer innerhalb der letzten fünf Jahre nach einer Verurteilung zu mindestens sechs Monaten Freiheitsstrafe erneut delinquiert hatte (angefochtenes Urteil, S. 5 f.). Der Aufschub der ausgefällten Sanktion ist diesfalls nur zulässig, wenn besonders günstige Umstände vorliegen, was die Vorinstanz verneinte. Konkret wurde der Beschwerdeführer in den vergangenen Jahren einmal zu einer Freiheitsstrafe von mindestens 6 Monaten verurteilt: Am 24. August 2004 bestätigte das Obergericht des Kantons Thurgau eine am 26. Juni 2003 erstinstanzlich ausgesprochene Gefängnisstrafe von 6 Monaten. Als massgeblicher Zeitpunkt für die Berechnung der Fünfjahresfrist ist - wie die Vorinstanz zu Recht bemerkt - auf den Zeitpunkt der Eröffnung des erstinstanzlichen Urteils abzustellen (so auch SCHNEIDER/GARRÉ, in: Basler Kommentar, Strafrecht, 2. Aufl. 2007, <ref-law> N 89), die hier am 4. November 2003 erfolgt ist. Die dem vorliegenden Verfahren zugrunde liegenden Delikte verübte der Beschwerdeführer zwischen Ende Juni 2004 und Ende Mai 2005, mithin innerhalb der in <ref-law> vorgesehenen Zeitspanne von 5 Jahren zwischen der früheren Verurteilung und der neuen Tat. Die Anwendung dieser Bestimmung ist somit nicht zu beanstanden.
2. Der Beschwerdeführer beantragt die Gewährung des bedingten Vollzugs für die ausgesprochene Sanktion von 720 Stunden gemeinnütziger Arbeit. <ref-law> setzt hierfür das Vorliegen besonders günstiger Umstände voraus.
2.1 Nach der bundesgerichtlichen Rechtsprechung sind unter besonders günstigen Umständen solche zu verstehen, die ausschliessen, dass die Vortat die Prognose verschlechtert. Bei <ref-law> gilt demnach die Vermutung einer günstigen Prognose bzw. des Fehlens einer ungünstigen Prognose nicht. Vielmehr kommt der früheren Verurteilung zunächst die Bedeutung eines Indizes für die Befürchtung zu, dass der Täter weitere Straftaten begehen könnte. Die Gewährung des bedingten Strafvollzuges kommt daher nur in Betracht, wenn eine Gesamtwürdigung aller massgebenden Faktoren den Schluss zulässt, dass trotz der Vortat eine begründete Aussicht auf Bewährung besteht. Dabei ist zu prüfen, ob die indizielle Befürchtung durch die besonders günstigen Umstände zumindest kompensiert wird. Das trifft etwa zu, wenn die neuerliche Straftat mit der früheren Verurteilung in keinerlei Zusammenhang steht, oder bei einer besonders positiven Veränderung in den Lebensumständen des Täters. Jedenfalls ist bei eindeutig günstiger Prognose der Strafaufschub stets zu gewähren. Die Vorschrift von <ref-law> stellt klar, dass der Rückfall für sich genommen den bedingten Strafvollzug nicht auszuschliessen vermag (<ref-ruling> E. 4.2.3 S. 6 f. mit Hinweisen).
2.2 Die Vorinstanz führt aus, dass sich der Beschwerdeführer seit der letzten Verurteilung vom 31. August 2006/2. Oktober 2006 nichts mehr zuschulden kommen liess und dass er "offensichtlich einer geregelten Erwerbstätigkeit" nachgehe. Ferner falle positiv ins Gewicht, dass die Steuern bezahlt worden seien. Obwohl "in gewisser Weise" eine positive Entwicklung des Beschwerdeführers angenommen wurde, verneinte das Obergericht eine dauerhafte Veränderung in den Lebensumständen, so dass "(noch) keine eindeutig günstige Prognose gestellt werden" könne, zumal aufgrund der vielen Vorstrafen sowie ungünstiger Führungsberichte. Weiter bestehe Unklarheit hinsichtlich der Schuldensituation sowie der längerfristigen Beschäftigung des Beschwerdeführers. Aktuelle Unterlagen fehlten und die Vorbringen des Beschwerdeführers blieben "unbestimmt und schwammig" (angefochtenes Urteil, S. 10 f.).
2.3 Der Beschwerdeführer macht geltend, dass es gegen ihn seit bald drei Jahren keinerlei Strafverfahren und Verurteilungen mehr gegeben habe, dass er einer geregelten Arbeit nachgehe, seine finanziellen Probleme löse und nicht mehr vom Sozialdienst abhängig sei. Die Vorinstanz habe zudem die von der ersten Instanz festgestellten positiven Veränderungen nicht berücksichtigt. Die Taten lägen im Übrigen lange zurück, was sich strafmildernd auswirken sollte. Der Beschwerdeführer weist schliesslich darauf hin, dass nach dem ihm zugestellten schriftlichen Urteilsdispositiv der ersten Instanz der bedingte Vollzug für die gemeinnützige Arbeit gewährt worden sei, was später später als Irrtum bezeichnet und mit Zustellung des Urteilstextes korrigiert worden sei. Dieser Verfahrensfehler sei strafmildernd zu berücksichtigen (Beschwerde, S. 2 f.).
2.4 Die Beurteilung der Gewährung des bedingten Strafvollzugs bildet Teil der Strafzumessung, bei welcher dem Sachrichter nach konstanter bundesgerichtlicher Rechtsprechung (vgl. zuletzt <ref-ruling> E. 6.1) ein erheblicher Spielraum des Ermessens zusteht. Für die Anwendung von <ref-law> gelten diesbezüglich die gleichen Massstäbe. Das Bundesgericht greift in diesen Ermessensspielraum nur ein, wenn der Sachrichter von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wenn er wesentliche Gesichtspunkte ausser Acht gelassen bzw. in Überschreitung oder Missbrauch seines Ermessens falsch gewichtet hat (<ref-ruling> E. 6.1). Dies ist vorliegend nicht der Fall. Die Vorinstanz hat die massgebenden Faktoren zutreffend gewürdigt. Die Verneinung besonders günstiger Umstände durch die Vorinstanz ist im Ergebnis nicht zu beanstanden. Dass im zugestellten schriftlichen Urteilsdispositiv der ersten Instanz irrtümlicherweise die Gewährung des bedingten Strafvollzugs aufgeführt war, was mit Zustellung des - massgeblichen - Urteilstextes korrigiert wurde, stellt entgegen der Ansicht des Beschwerdeführers keinen sanktionswirksamen Verfahrensfehler dar. Das erstinstanzliche Urteil erging am 7. Februar 2008, das Urteil des Obergerichts am 16. Oktober 2008. Eine übermässige Verfahrenslänge, welche sich nach Ansicht des Beschwerdeführers strafmildernd auswirken müsste, kann hieraus nicht abgeleitet werden.
3. Die Beschwerde ist nach dem Gesagten abzuweisen. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Kosten des Verfahrens (<ref-law>). Er stellt indes ein Gesuch um unentgeltliche Rechtspflege gemäss Art. 64 Abs. 1 und 2 BGG. Dieses kann bewilligt werden, wenn von seiner Bedürftigkeit auszugehen und diese ausreichend belegt ist sowie seine Beschwerde nicht von vornherein aussichtslos war (zum Ganzen <ref-ruling> E. 4 S. 164 f.). Dem Beschwerdeführer und Gesuchsteller obliegt es, seine eigenen Einkommens- und Vermögensverhältnisse umfassend darzulegen und soweit wie möglich zu belegen. Praxisgemäss weist das Bundesgericht die Bewilligung der unentgeltlichen Rechtspflege ab, wenn der Gesuchsteller seinen Obliegenheiten nicht nachkommt.
Der Gesuchsteller begnügt sich mit dem Hinweis, dass sich seine Bedürftigkeit aus den Akten ergebe. Dieser pauschale Hinweis stellt keine rechtsgenügliche Begründung dar. Er zeigt auch nicht auf, inwiefern zur Wahrung seiner Rechte eine anwaltliche Vertretung notwendig wäre. Dem Beschwerdeführer sind deshalb die vollen Kosten aufzuerlegen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Thurgau schriftlich mitgeteilt.
Lausanne, 20. Mai 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Keller