Sachverhalt:
A. Das Strafgericht des Kantons Basel-Stadt verurteilte X._ am 3. November 2006 wegen versuchten Betruges zu 12 Monaten Gefängnis. Im selben Verfahren wurden K._, L._ und M._ wegen teilweise versuchten, teilweise gewerbsmässigen Betruges verurteilt.
B. Das Appellationsgericht bestätigte am 29. Oktober 2008 den erstinstanzlichen Schuldspruch gegen X._ und verurteilte ihn zu einer Freiheitsstrafe von 12 Monaten, unter Anrechnung der Untersuchungshaft.
C. Gegen dieses Urteil erhebt X._ Beschwerde in Strafsachen. Er beantragt einen Freispruch. Eventualiter sei er zu einer Geldstrafe von 360 Tagessätzen zu verurteilen. Die Höhe des Tagessatzes sei vom Gericht zu bestimmen. Weiter stellt er ein Gesuch um Gewährung der unentgeltlichen Rechtspflege.

Erwägungen:
1. 1.1 Der Beschwerdeführer rügt, er habe nicht die Absicht gehabt, zukünftige Kundengelder ihrem Zweck zu entfremden oder sich daran zu bereichern. Damit wendet er sich gegen die tatsächlichen Feststellungen der Vorinstanz zu seinem Tatwillen.
1.2 Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Für derartige Rügen gelten die gleichen Begründungsanforderungen, wie sie gestützt auf Art. 90 Abs. 1 lit. b OG für die staatsrechtliche Beschwerde gegolten haben. Die Beschwerdeschrift muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Entscheid verletzt worden sind. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen. Auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein. Wird eine Verletzung des Willkürverbots geltend gemacht, muss im Einzelnen dargelegt werden, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.4.3 S. 254 f. mit Hinweisen).
1.3 Der Beschwerdeführer legt in Ziffern 9 bis 15, 17 und 18 seiner Beschwerdeschrift dar, wie er die vorhandenen Beweise gewürdigt hätte bzw. welche Erwägungen der Vorinstanz er für falsch hält. Er begründet jedoch nicht, weshalb diese Sachverhaltsfeststellungen offensichtlich unrichtig bzw. willkürlich im Sinne von <ref-law> sein sollen. Seine Rügen beschränken sich auf appellatorische Kritik, auf welche nicht einzutreten ist.
1.4 Der Beschwerdeführer macht in Ziffer 16 der Beschwerde geltend, die Vorinstanz gehe nicht auf die Aussagen des Zeugen Z._ ein, wonach er (der Beschwerdeführer) ihm ein Anlageprojekt in Kroatien vorgeschlagen habe. Sie bewerte alle seine Projekte als Hochstapeleien, obwohl sie gleichzeitig ausführe, er sei aufgrund seiner beruflichen Ausbildung und Erfahrung den anderen Angeschuldigten überlegen gewesen. Mit seinen Vorbringen rügt er sinngemäss eine willkürliche Beweiswürdigung nach <ref-law> sowie die aus dem Anspruch des rechtlichen Gehörs nach <ref-law> fliessende Begründungspflicht.
1.5 Die Vorinstanz erwägt, bei der Y._ Holding AG habe es sich um eine blosse Kulisse gehandelt. Es sei nicht geplant gewesen, Investitionen in gewinnbringende Anlagen zu tätigen. Der Beschwerdeführer habe nach seiner eigenen Aussage das Geld der ersten beiden Kunden für die Mietkaution einsetzen wollen. Auch der Mitangeklagte L._ belaste ihn. Gemäss seinen Aussagen habe der Beschwerdeführer die fingierten Darlehensverträge erstellt. Er sei der Denker und den anderen weit überlegen gewesen. Beim Treffen mit dem verdeckten Ermittler habe er ein von ihm selbst erstelltes fingiertes Schreiben einer Bank vorgelegt, wonach für die Y._ Holding AG Depotwerte in Millionenhöhe bestanden hätten. Er habe das vom verdeckten Ermittler eingebrachte Geld zweckfremd einsetzen wollen, was sich aus einer von ihm erstellten Liste ergebe. Die dem verdeckten Ermittler vorgeschlagenen Anlagekonzepte seien auffällig vielfältig gewesen. Er habe die vorgelegten Dokumente mit einem Hintergrund versehen, indem er Namen erwähnt habe. Weiter habe er über Anlagekonzepte auf Kuba gesprochen. Das Anlagekapital des verdeckten Ermittlers hätte mittels einer Versicherung in Malta und London abgesichert werden sollen. Dazu habe er eine fingierte Versicherungspolice vorbereitet, welche noch nicht unterzeichnet gewesen sei. Seine Anpreisungen entbehrten jeglicher Grundlage und seien pure Hochstapelei. Er habe anlässlich der Befragung im Untersuchungsverfahren zu zwei Anlageprojekten ("altersgerechtes Wohnen in Mariastein" und "Hotel- und Ländereiprojekt in Kroatien") über eines ("altersgerechtes Wohnen in Mariastein") keine genaueren Angaben machen können.
1.6 Die Vorinstanz musste sich nicht ausdrücklich mit jeder tatbeständlichen Behauptung und jedem rechtlichen Einwand auseinandersetzen. Vielmehr durfte sie sich auf die für den Entscheid wesentlichen Gesichtspunkte beschränken (vgl. <ref-ruling> E. 3.1 S. 277 mit Hinweisen). Dass sie sich nicht mit der Aussage des Zeugen Z._ befasste, ist nicht willkürlich und verletzt die aus dem Grundsatz des rechtlichen Gehörs nach <ref-law> fliessende Begründungspflicht nicht. Der Beschwerdeführer legt nicht substantiiert dar, was diese Zeugenaussage im Gesamtbild der umfassenden Beweiswürdigung der Vorinstanz zur seiner Entlastung beitragen könnte. Kein Widerspruch besteht darin, dass die Vorinstanz den Beschwerdeführer einerseits als beruflich gut qualifiziert erachtet, andererseits seine Projekte als Hochstapelei bewertet. Die Ausbildung lässt jedenfalls keinen Schluss auf das konkrete Geschäftsgebaren zu. Die Rüge erweist sich als unbegründet.
2. 2.1 Der Beschwerdeführer macht geltend, der Einsatz des verdeckten Ermittlers E._ verstosse gegen Art. 4 Abs. 1 lit. a des Bundesgesetzes vom 20. Juni 2003 über die verdeckte Ermittlung (BVE, SR 312.8). Am 26. März 2006 (recte: 26. April 2006) habe der verdeckte Ermittler telefonisch Kontakt mit der Y._ Holding AG aufgenommen und einen Besprechungstermin auf den 28. April 2006 vereinbart. Die Staatsanwaltschaft habe bereits am 27. März 2006 die Genehmigung der verdeckten Ermittlung durch den Haftrichter eingeholt. Im Zeitpunkt der Genehmigung der verdeckten Ermittlung habe die Y._ Holding AG aber noch keine Geschäftstätigkeiten mit strafrechtlicher Relevanz aufgenommen, sondern sei mit dem Aufbau der Firma beschäftigt gewesen. Die Schwelle zum Versuch sei in diesem Zeitpunkt noch nicht überschritten gewesen. Auch wenn die Angeklagten im Begriff gewesen seien, alle Vorkehrungen für eine Geschäftseröffnung zu treffen, hätten sie bis zum Einsatz des verdeckten Ermittlers von ihrem Vorhaben zurücktreten können. Bis dahin seien keine Straftaten begangen worden, noch aufgrund von hinreichenden objektiven Gesichtspunkten voraussehbar gewesen. Daher sei die Aussage des verdeckten Ermittlers nicht verwertbar.
2.2 Die Vorinstanz führt aus, zum Einsatz des verdeckten Ermittlers genüge es, dass aufgrund bestimmter Tatsachen der Verdacht bestehe, es würden im BVE aufgeführte Straftaten begangen. Im Zeitpunkt der Ermittlung habe der Tatverdacht auf gewerbsmässige, bandenmässige und mehrfache Betrugsdelikte bestanden. Der Deliktsbetrag von Euro 30'000.-- sei nicht unerheblich. Für den Einsatz eines verdeckten Ermittlers sei es nicht erforderlich, dass der Tatverdacht dringend sei. Die Y._ Holding AG habe Kunden akquirieren wollen und dazu diverse Anlageangebote sowie einen fingierten Darlehensvertrag erstellt. Die Beteiligten hätten einen Aktienmantel gekauft, Büroräumlichkeiten angemietet und ein falsches Anwaltsschild angebracht. Damit hätten Tatsachen bestanden, die einen Verdacht auf Begehung künftiger Straftaten begründeten.
2.3 Gemäss Art. 4 Abs. 1 BVE kann eine verdeckte Ermittlung angeordnet werden, wenn bestimmte Tatsachen den Verdacht begründen, besonders schwere Straftaten seien begangen worden oder sollen voraussichtlich begangen werden (lit. a) und wenn andere Untersuchungshandlungen erfolglos geblieben sind, oder die Ermittlungen sonst aussichtslos wären oder unverhältnismässig erschwert würden (lit. b). Eine verdeckte Ermittlung kann schon angeordnet werden, wenn aufgrund bestimmter Tatsachen der Verdacht besteht, dass voraussichtlich besonders schwere Straftaten begangen werden sollen (<ref-ruling> E. 4.1.1 S. 280). Ein einfacher Verdacht reicht aus, ein dringender Tatverdacht ist nicht Voraussetzung (WOLFGANG WOHLERS, Das Bundesgesetz über die verdeckte Ermittlung (BVE), ZSR 124 (2005) I S. 226). Die Formulierung des "dringenden Tatverdachts" wurde in der parlamentarischen Beratung verworfen (AB 2002 N 1262 ff.; AB 2003 N 361 ff.).
2.4 Gestützt auf den von der Vorinstanz festgestellten Sachverhalt bestand im Zeitpunkt der Genehmigung der verdeckten Ermittlung ein hinreichender Verdacht, dass die vier Tatbeteiligten, darunter der Beschwerdeführer, im Begriff waren, Betrugsdelikte zu begehen. Sie bemühten sich, mittels der Y._ Holding AG Kunden anzuwerben, erstellten einen fingierten Darlehensvertrag, kauften einen Aktienmantel, mieteten Büroräumlichkeiten und brachten ein unechtes Anwaltsschild an. Diese Indizien reichen aus, um einen Verdacht bezüglich künftiger Vermögensdelikte zu begründen. Die Anordnung der verdeckten Ermittlung erweist sich als bundesrechtskonform.
3. 3.1 Der Beschwerdeführer rügt, der verdeckte Ermittler habe die Schwere der Straftat beeinflusst und dadurch Art. 10 Abs. 1 BVE verletzt. Der vom verdeckten Ermittler angebotene Betrag von Euro 300'000.-- übersteige die mögliche Minimalanlage um ein Vielfaches. In den von der Telefonkontrolle erfassten Gesprächen sei von diesem Betrag keine Rede gewesen. Die Tatbereitschaft zum Betrug sei insoweit durch den Auftritt des verdeckten Ermittlers hervorgerufen worden. Deshalb seien seine Aussagen unverwertbar.
3.2 Die Vorinstanz erwägt, der Beschwerdeführer habe mit dem verdeckten Ermittler über eine minimale anzulegende Summe von Euro 30'000.-- gesprochen. Obwohl tatsächlich Euro 300'000.-- übergeben worden seien, sei zu Gunsten des Beschwerdeführers vom niedrigeren Betrag auszugehen. Von einer Tatprovokation durch den verdeckten Ermittler könne nicht gesprochen werden, da der Beschwerdeführer und die anderen drei Tatbeteiligten bereits Veranstaltungen zur Deliktsbegehung getroffen hätten (Firmengründung, Miete von Büroräumlichkeiten, Erstellen von Dokumentationen, Besprechungen und Telefonate mit Kunden). Sie seien ohnehin bereit und willens gewesen, Geld entgegen zu nehmen.
3.3 Gemäss Art. 10 BVE dürfen die Ermittler keine allgemeine Tatbereitschaft wecken und die Tatbereitschaft nicht auf schwerere Straftaten lenken. Sie haben sich auf die Konkretisierung eines bereits vorhandenen Tatentschlusses zu beschränken (Abs. 1). Ihre Tätigkeit darf für den Entschluss zu einer konkreten Straftat nur von untergeordneter Bedeutung sein (Abs. 2). Eine allgemeine Tatbereitschaft hat der verdeckte Ermittler E._ nicht geweckt. Eine solche bestand schon im Zeitpunkt seines Einsatzes, wie sich aus den verschiedensten Vorkehrungen des Beschwerdeführers und seiner Mittäter ergibt. In Bezug auf die Straftat war es der Beschwerdeführer selbst, der auf Nachfrage des verdeckten Ermittlers den Betrag von Euro 30'000.-- als mindestens anzulegende Geldsumme vorgeschlagen hat. Die Vorinstanz verletzt kein Bundesrecht, wenn sie für den Betrag von Euro 30'000.-- eine Tatprovokation durch den verdeckten Ermittler verneint. Dessen Aussagen sind daher in Bezug auf den Betrag von Euro 30'000.-- vollumfänglich verwertbar.
4. 4.1 Der Beschwerdeführer rügt, die Vorinstanz verstosse gegen Bundesrecht, indem sie ihm anstelle einer Geldstrafe von 360 Tagessätzen eine unbedingte Freiheitsstrafe von 12 Monaten auferlege. Die Geldstrafe stelle im Bereich von Strafen bis zu 360 Tagessätzen die Hauptsanktion dar. Im Regelfall sei bei alternativ zur Verfügung stehenden Strafen jene auszusprechen, welche weniger stark in die persönliche Freiheit eingreift. Freiheitsstrafen dürften nur verhängt werden, wenn der Staat keine anderen Mittel habe, um die öffentliche Sicherheit zu gewährleisten. Im angefochtenen Urteil seien keine solchen Gründe genannt worden. Zwar sei die Eintreibung der Geldstrafe auf dem Betreibungsweg gegen den Beschwerdeführer im Moment nicht erfolgversprechend. Es bestehe aber kein Hinweis, dass sich der Beschwerdeführer weigern werde, eine Geldstrafe freiwillig zu bezahlen. Die gegen ihn laufenden Betreibungen liessen nicht den Schluss zu, dass er die Geldstrafe nicht bezahlen werde. Überdies verletze die Vorinstanz ihre aus <ref-law> fliessende Begründungspflicht, da sie mit einem einzigen Satz, wonach eine Geldstrafe offensichtlich uneinbringlich sei, die Verweigerung dieser Strafart begründe.
Mit seinen Ausführungen zur Strafzumessung wendet sich der Beschwerdeführer einzig gegen die ausgesprochene Strafart, nicht aber das Strafmass. Dies ergibt sich daraus, dass er dasselbe Strafmass (360 Tagesätze Geldstrafe) verlangt, welches demjenigen entspricht, das die Vorinstanz ausgesprochen hat (12 Monate Freiheitsstrafe). Auch wenn er am Rande sinngemäss den Einbezug der verdeckten Ermittlung als Strafminderungsgrund in die Strafzumessung verlangt, so bringt er mit seinem Antrag zum Strafmass zum Ausdruck, dass die Vorinstanz die verdeckte Ermittlung bei der Strafzumessung nach seiner Auffassung hinreichend berücksichtigt hat. Unter diesen Umständen ist einzig die Strafart zu prüfen.
4.2 Für den Bereich der mittleren Kriminalität sieht das neue Recht als Regelsanktion die Geldstrafe und die Freiheitsstrafe vor (Art. 34 und 40 StGB). Die Geldstrafe beträgt höchstens 360 Tagessätze (<ref-law>), die Freiheitsstrafe in der Regel mindestens sechs Monate (<ref-law>). Nach der Konzeption des neuen Allgemeinen Teils des Strafgesetzbuches stellt die Geldstrafe die Hauptsanktion dar. Freiheitsstrafen sollen nur verhängt werden, wenn der Staat keine anderen Mittel hat, die öffentliche Sicherheit zu gewährleisten. Nach dem Prinzip der Verhältnismässigkeit soll bei alternativ zur Verfügung stehenden und hinsichtlich des Schuldausgleichs äquivalenten Sanktionen im Regelfall diejenige gewählt werden, die weniger stark in die persönliche Freiheit des Betroffenen eingreift bzw. die ihn am wenigsten hart trifft (<ref-ruling> E. 4.2.1 S. 101 mit Hinweisen). Wo verschiedene Sanktionen zur Verfügung stehen, gehört zur Strafzumessung nebst der Bestimmung des Strafmasses auch die Festlegung der Strafart. Die Wahl der Sanktionsart erfolgt alleine durch das Gericht. Dem Verurteilten steht diesbezüglich kein Wahlrecht zu. Massgebende Kriterien sind die Zweckmässigkeit einer Sanktion, die Auswirkungen auf den Täter und sein soziales Umfeld sowie ihre präventive Wirksamkeit (<ref-ruling> E. 6.3.3.3 S. 109 und E. 6.3.3.4 S. 110). <ref-law> bestimmt unter dem Titel Begründungspflicht, dass das Gericht in der Begründung die für die Zumessung der Strafe erheblichen Umstände und deren Gewichtung festhält (vgl. Entscheid 6B_472/2007 vom 27. Oktober 2007 E. 8.1). Das Gericht hat auch die Wahl der Strafart im Urteil zu begründen (<ref-law>).
4.3 Die Vorinstanz führt zur Strafzumessung aus, der Beschwerdeführer weise Betreibungen von über einer halben Million Franken und Verlustscheine im Betrag von ca. Fr. 130'000.-- auf. Deshalb sei von der offensichtlichen Uneinbringlichkeit einer Geldstrafe auszugehen und eine Freiheitsstrafe auszusprechen. Sie verweigert ihm den bedingten Strafvollzug unter Hinweis auf die einschlägigen Vorstrafen. Im Übrigen verweist sie auf die erstinstanzliche Urteilsbegründung. Daraus ergibt sich, dass der Beschwerdeführer über mehrere einschlägige Vorstrafen aus den Jahren 1999, 2000 und 2002 verfügt. Damals wurde er wegen Betrugshandlungen zu jeweils mehrjährigen Freiheitsstrafen verurteilt. Er verbüsste zwei Jahre Haft in Deutschland sowie bis Anfang September 2002 eine weitere Freiheitsstrafe in Frankreich. Aufgrund der Vorstrafen geht die erste Instanz davon aus, dass der Beschwerdeführer nicht einsichtig ist.
4.4 Die Vorinstanz hat in ihrer Begründung die für sie entscheiderheblichen Kriterien zur Wahl der Strafart, nämlich die Vorstrafen und die finanzielle Situation des Beschwerdeführers, erwähnt. Sie durfte im Übrigen auf die erstinstanzlichen Erwägungen verweisen. Die Argumentation des Beschwerdeführers, die Vorinstanz verletze bei der Festsetzung der Strafart ihre Begründungspflicht nach <ref-law>, geht fehl.
Vor dem gesamten Hindergrund, insbesondere mit Blick auf die einschlägigen Vorstrafen und des auch von einem mehrjährigen Freiheitsentzug unbeeindruckten Beschwerdeführers, durfte die Vorinstanz vielmehr ohne Bundesrechtsverletzung davon ausgehen, dass nicht eine Geldstrafe, sondern ausschliesslich eine Freiheitsstrafe als angemessene und zweckmässige Sanktion in Frage kommt. Die Rüge des Beschwerdeführers, die Vorinstanz verletze bei der Festsetzung der Strafart Bundesrecht, erweist sich als unbegründet.
5. Der Beschwerdeführer macht geltend, die unterschiedliche Strafzumessung der Mitangeklagten verstosse gegen seinen Anspruch auf Rechtsgleichheit nach <ref-law>. Er übersieht dabei, dass die Mitangeklagten K._ und M._, welche ebenfalls wegen versuchten Betruges schuldig erklärt wurden, im Gegensatz zu ihm nicht einschlägig vorbestraft sind. Nicht vergleichbar ist der Fall des Beschwerdeführers mit dem Mitangeklagten L._, weil letzterer wegen der schwereren Taten, nämlich mehrfachen gewerbsmässigen Betrugs und versuchten Betrugs, zu einer Freiheitsstrafe von 14 Monaten verurteilt wurde. Die unterschiedlichen Vorstrafen und die teilweise anderslautenden Schuldsprüche führen dazu, dass die Zweckmässigkeit der Strafart beim Beschwerdeführer und den Mitangeklagten unterschiedlich beurteilt werden kann. Die Rüge erweist sich als insoweit unbegründet.
6. Die Beschwerde ist insgesamt abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Das Gesuch des Beschwerdeführers um Gewährung der unentgeltlichen Rechtspflege ist abzuweisen, da die Beschwerde von vornherein aussichtslos war. Seinen angespannten finanziellen Verhältnissen ist bei der Bemessung der Gerichtskosten Rechnung zu tragen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 25. Juni 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Koch