Sachverhalt:
A. Das Strafgericht Basel-Stadt sprach Y._ am 26. Januar 2007 des mehrfachen gewerbsmässigen Betrugs, der mehrfachen Urkundenfälschung sowie der mehrfachen Geldwäscherei schuldig und bestrafte ihn mit einer Freiheitsstrafe von 4 Jahren. Es verurteilte Y._ in solidarischer Haftung mit Z._ zur Bezahlung von Fr. 10'000.-- Schadenersatz an D._ und behaftete ihn bei der teilweisen Anerkennung der Schadenersatzforderung der Zivilkläger aA._ und bA._ im Umfang von Fr. 29'000.--. Deren Mehrforderungen und Genugtuungsansprüche verwies es auf den Zivilweg.
Auf Appellation von Y._ hin bestätigte das Appellationsgericht des Kantons Basel-Stadt am 20. März 2009 das erstinstanzliche Urteil.
B. Y._ beantragt mit Beschwerde in Strafsachen, die Urteile des Appellationsgerichts vom 20. März 2009 und des Strafgerichts vom 26. Januar 2007 aufzuheben und ihn freizusprechen, eventualiter wegen Gehilfenschaft zu mehrfachem Betrug, zu mehrfacher Urkundenfälschung und zu mehrfacher Geldwäscherei zu einer Freiheitsstrafe von 2 Jahren, davon 1 Jahr bedingt, zu verurteilen. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung.
C. Vernehmlassungen wurden keine eingeholt.

Erwägungen:
1. Die Beschwerde in Strafsachen ist zulässig gegen Entscheide der letzten kantonalen Instanz (<ref-law>). Soweit der Beschwerdeführer auch die Aufhebung des Urteils des Strafgerichts vom 26. Januar 2007 beantragt, ist auf die Beschwerde nicht einzutreten.
2. Die Vorinstanz hält folgende Sachverhalte für erwiesen:
2.1 Z._ und der Beschwerdeführer teilten aA._ und bA._ wahrheitswidrig mit, Peter Hüsy, ein enger Mitarbeiter von Bundesrätin Calmy-Rey, suche nach Möglichkeiten, 1'000 ausländische Arbeitskräfte für die NEAT in die Schweiz zu holen. aA._ schlug vor, die Arbeitskräfte in Tunesien zu suchen und sagte hierfür die Mithilfe seiner aus Tunesien stammenden Ehegattin bA._ zu. Dieser gelang es, in Tunesien in ihrem Familien- und Bekanntenkreis ca. 500 Arbeitskräfte zu rekrutieren. Z._ und der Beschwerdeführer verlangten von den Arbeitsinteressenten je Fr. 650.--, angeblich als Vorauszahlung für Visum, Aufenthalts- und Arbeitsbewilligung, Reisekosten sowie Versicherungsschutz. Da es sich als unmöglich erwies, von Tunesien aus Geld in die Schweiz zu senden, fungierte das Ehepaar A._ als Zahlstelle und schoss selber erhebliche Beträge vor. Die Zahlungen erfolgten zugunsten eines Kontos der V._ Ltd. und später der W._ Ltd. bei einer irischen bzw. englischen Bank, über welche Z._ und der Beschwerdeführer je alleine verfügen konnten. bA._, die der Sache nicht traute, wollte den Mitarbeiter des EDA persönlich kennen lernen, woraufhin ein Treffen organisiert wurde, anlässlich dessen X._ sich als Peter Hüsy ausgab. Den Interessenten in Tunesien wurden gefälschte Dokumente und Verträge ausgehändigt. Der Schwindel flog auf, als am Tag der geplanten Abreise das versprochene Flugzeug nicht bereit stand. bA._ und aA._ wurden in Tunesien verhaftet und bis zu ihrer Verurteilung mehrere Monate in Haft gehalten. bA._ gebar dort ihr zweites Kind. Die Ehegatten wurden erst vom zweitinstanzlichen Gericht milder verurteilt, so dass sie wieder in die Schweiz zurückkehren konnten. Die von ihnen einbezahlten Gelder von fast Fr. 300'000.-- wurden nicht zurückerstattet.
2.2 Z._, als Agent der V._ Ltd., versprach E._ und D._ zwei Kredite von je Fr. 50'000.--. E._ und D._ sollten zuerst je Fr. 10'000.-- zwecks Abschluss einer Versicherung mit der V._ Ltd. bezahlen. Nach Unterzeichnung der Kreditverträge und Bezahlung der Einlagen von je Fr. 10'000.-- wurden E._ und D._ Versicherungspolicen der V._ Ltd. ausgehändigt. Der versprochene Kredit wurde nicht vergeben. E._ erhielt die Fr. 10'000.-- zurückerstattet, nicht jedoch D._.
3. 3.1 Der Beschwerdeführer rügt eine Verletzung des Grundsatzes in dubio pro reo (Beschwerde Ziff. 10 S. 10). Es lägen weder Beweise noch Indizien für den ihm vorgeworfenen Tatbeitrag vor. Er habe im Zusammenhang mit den Straftaten zum Nachteil der Ehegatten A._ lediglich einige Schreiben für Z._ aufgesetzt, sei jedoch über dessen Vorhaben nicht informiert gewesen und nur am Rande des Geschehens als unbeteiligter Begleiter von Z._ in Erscheinung getreten. Er habe nie die Absicht gehabt, sich zu bereichern oder Dritte zu schädigen.
Auch bezüglich des gewerbsmässigen Betrugs zum Nachteil von D._ beständen keinerlei Beweise gegen ihn. Es habe keine Kontakte zwischen ihm und E._ bzw. D._ gegeben. Das Anfertigen von Musterverträgen und Dokumenten auf dem Computer stelle noch keine verbotene Handlung dar (Beschwerde Ziff. 21 S. 16).
3.2 Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie willkürlich 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>, vgl. auch <ref-law>; <ref-ruling> E. 1.4.1). Die Rüge der Willkür muss präzise vorgebracht und begründet werden, ansonsten darauf nicht eingetreten wird (<ref-law>; <ref-ruling> E. 2.2; <ref-ruling> E. 1.4.3).
Willkür bei der Beweiswürdigung nach <ref-law> liegt vor, wenn die Behörde von Tatsachen ausgeht, die mit der tatsächlichen Situation in klarem Widerspruch stehen oder auf einem offenkundigen Fehler beruhen. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung oder Würdigung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre, genügt für die Annahme von Willkür nicht (<ref-ruling> E. 5.4; <ref-ruling> E. 2b, je mit Hinweisen). Dem Grundsatz in dubio pro reo kommt als Beweiswürdigungsregel keine über das Willkürverbot von <ref-law> hinausgehende selbständige Bedeutung zu (<ref-ruling> E. 2a; <ref-ruling> E. 2a, je mit Hinweisen).
3.3 Der Beschwerdeführer war gemäss den Ehegatten A._ bei vielen Gesprächen mit ihnen anwesend. Er habe sich sehr geärgert, dass aus Tunesien kein Geld in die Schweiz transferiert werden konnte und diesbezüglich selber Abklärungen getroffen. Er war es auch, der aA._ das Flugticket für die Reise nach Tunesien übergab, nachdem bA._ in Tunesien bereits verhaftet worden war, und X._ für das Rollenspiel als Peter Hüsy aufbot. Im Notebook des Beschwerdeführers wurde eine CD-Rom sichergestellt, auf der sich vorgefertigte Versicherungsausweise für die tunesischen Arbeitskräfte und ein Schreiben mitsamt Entwurf von Peter Hüsy an Z._, welches aA._ vom Beschwerdeführer ausgehändigt erhielt, befanden. Ferner enthielt die CD-Rom vorgefertigte Versicherungspolicen, die mit den an E._ und D._ ausgehändigten identisch sind, ein Schreiben an E._ sowie weitere Dokumente, welche den Schluss zulassen, dass der Besitzer der CD-Rom aktiv in der Betrugssache zum Nachteil der Ehegatten A._ und D._ mitwirkte. In der Wohnung des Beschwerdeführers wurde ein Fax von E._ und D._ an die V._ Ltd. sichergestellt. Die Vorinstanz weist schliesslich darauf hin, dass der Beschwerdeführer, im Gegensatz zum sprachlich unbeholfenen Z._, aufgrund seiner Intelligenz und seiner Ausbildung als Ökonom in der Lage war, auch fremdsprachige Dokumente zu formulieren und zu gestalten. Der Beschwerdeführer profitierte finanziell von der Straftat, da er neben Z._ als einziger Zugriff auf die Konten der V._ Ltd. und der W._ Ltd. hatte und während dessen Inhaftierung auch tatsächlich Geld abhob. Nicht willkürlich ist daher der vorinstanzliche Beweisschluss, der Beschwerdeführer sei als mehrheitlich im Hintergrund tätiger intellektueller Verfasser und Drahtzieher in gleichem Masse wie Z._ am Betrug zum Nachteil der Ehegatten A._ bzw. der tunesischen Arbeitsinteressenten und D._ beteiligt gewesen.
3.4 Der Beschwerdeführer wendet ein, neben Z._ und ihm hätten weitere Personen Zutritt zu den Büroräumlichkeiten gehabt, in welchen sich sein nicht passwortgeschütztes Notebook befand. In ihrem Umfeld sei es üblich gewesen, dass Bekannte den Computer mitbenützten. Es sei daher auch nicht ungewöhnlich, dass jemand die CD-Rom in seinem Notebook vergass (Beschwerde Ziff. 4 S. 6 f.). Solche unbelegten und wenig substanziierten Behauptungen vermögen keine Willkür zu begründen. Im Übrigen beanstandet der Beschwerdeführer die vorinstanzlichen Ausführungen zur Beweiswürdigung in verschiedener Hinsicht als unzutreffend und spekulativ, ohne jedoch darzulegen, inwiefern die Sachverhaltsfeststellung im Ergebnis qualifiziert falsch und damit willkürlich sein soll. Darauf ist nicht einzutreten.
4. 4.1 Der Beschwerdeführer bringt vor, Z._ habe seit Beginn der Strafuntersuchung ausgesagt, er, Y._, habe mit der Sache nichts zu tun gehabt. Dies habe er im Laufe des Verfahrens vor dem Appellationsgericht zudem in einem Schreiben an ihn bestätigt. Die Vorinstanz habe seinen Antrag auf Einvernahme von Z._ im Appellationsverfahren zu Unrecht abgewiesen (Beschwerde Ziff. 5 S. 7).
4.2 Die Parteien haben Anspruch darauf, mit rechtzeitig und formgültig angebotenen Beweisanträgen und Vorbringen gehört zu werden, soweit diese erhebliche Tatsachen betreffen und nicht offensichtlich beweisuntauglich sind. Ein Verzicht auf die Abnahme von weiteren Beweisen ist zulässig, wenn sich das Gericht aufgrund der bereits erhobenen Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener Beweiswürdigung annehmen kann, dass die abgelehnten Beweisanträge nichts an seiner Überzeugung zu ändern vermögen (<ref-ruling> E. 5.3; <ref-ruling> E. 3; <ref-ruling> nicht publ. E. 2.1, mit Hinweisen).
4.3 Z._ bestritt auch seine eigene Strafbarkeit vehement und stellte sich anfänglich selber als Opfer von Peter Hüsy dar. Entsprechend zu würdigen sind auch seine Aussagen mit Bezug auf den Beschwerdeführer. Nicht unhaltbar sind die Erwägungen im angefochtenen Entscheid, wonach Z._ derart in den Betrugsfall verstrickt ist, dass die nach dem rechtskräftigen Schuldspruch erfolgte alleinige Übernahme der Verantwortung, aus welcher er keine nachteiligen Konsequenzen zu befürchten hatte, kein Glaube zu schenken sei. Die Vorinstanz durfte den Antrag auf Einvernahme von Z._ daher ohne Willkür in antizipierter Beweiswürdigung abweisen. Die Rüge ist unbegründet.
5. 5.1 Der Beschwerdeführer macht eine Verletzung von <ref-law> geltend. Die Ehegatten A._ hätten aus Gewinnsucht leichtgläubig der märchenhaften Geschichte von Z._ geglaubt. Ihre Blindheit sei nicht schützenswert, da es ihnen ein Leichtes gewesen wäre, die Angaben von Z._ zu überprüfen. Auch fehle es an einer unrechtmässigen Bereicherungsabsicht.
5.2 Des Betrugs nach <ref-law> macht sich namentlich schuldig, wer in der Absicht, sich oder einen andern unrechtmässig zu bereichern, jemanden durch Vorspiegelung oder Unterdrückung von Tatsachen arglistig irreführt und so den Irrenden zu einem Verhalten bestimmt, wodurch dieser sich selbst oder einen andern am Vermögen schädigt.
Arglist im Sinne von <ref-law> ist gegeben, wenn der Täter ein ganzes Lügengebäude errichtet oder sich besonderer Machenschaften oder Kniffe bedient. Ein Lügengebäude liegt vor, wenn mehrere Lügen derart raffiniert aufeinander abgestimmt sind und von besonderer Hinterhältigkeit zeugen, dass sich selbst eine kritische Person täuschen lässt. Als besondere Machenschaften gelten Erfindungen und Vorkehren sowie das Ausnützen von Begebenheiten, die allein oder gestützt auf Lügen oder Kniffe geeignet sind, den Betroffenen irrezuführen (<ref-ruling> E. 5.2 S. 81 mit Hinweisen). Dies wird in der Rechtsprechung insbesondere bejaht, wenn sich der Täter rechtswidrig erlangter, gefälschter oder verfälschter Urkunden und Belege bedient (<ref-ruling> E. 4.4.3; <ref-ruling> E. 3a).
Arglist scheidet aus, wenn der Getäuschte den Irrtum mit einem Mindestmass an Aufmerksamkeit hätte vermeiden können. Dabei ist die jeweilige Lage und Schutzbedürftigkeit des Betroffenen im Einzelfall entscheidend. Besondere Fachkenntnis und Geschäftserfahrung des Opfers sind in Rechnung zu stellen. Auch unter dem Gesichtspunkt der Opfermitverantwortung erfordert die Erfüllung des Tatbestands indes nicht, dass das Täuschungsopfer die grösstmögliche Sorgfalt walten lässt und alle erdenklichen Vorkehren trifft. Entsprechend entfällt der strafrechtliche Schutz nicht bei jeder Fahrlässigkeit des Getäuschten, sondern nur bei Leichtfertigkeit, welche das betrügerische Verhalten des Täters in den Hintergrund treten lässt (<ref-ruling> E. 5.2 S. 80 f.; <ref-ruling> E. 3a; <ref-ruling> E. 2a, je mit Hinweisen). Der Gesichtspunkt der Überprüfbarkeit erlangt nach der neueren Rechtsprechung auch bei Lügengebäuden und betrügerischen Machenschaften Bedeutung. Auch in diesen Fällen ist Arglist somit nicht gegeben, wenn das Täuschungsopfer die grundlegendsten Vorsichtsmassnahmen nicht beachtet hat (<ref-ruling> E. 5.2 S. 82; <ref-ruling> E. 2a).
5.3 Vorliegend ist aufgrund der Summierung der raffiniert aufeinander abgestimmten Lügen von einem Lügengebäude im Sinne der bundesgerichtlichen Rechtsprechung auszugehen. Die systematische Verwendung von gefälschten Urkunden und das inszenierte Treffen mit dem Mitarbeiter des EDA zeichnen sich im Vergleich zu einfachen Lügen durch höhere Anforderungen an die Vorbereitung, Durchführung und Wirkung der Täuschungshandlung aus und stellen nach der Rechtsprechung besondere Machenschaften dar.
Zutreffend ist, dass die Ehegatten A._ am Wahrheitsgehalt der ihnen vorgetragenen Geschichte, wonach ein Mitarbeiter des EDA auf informelle Weise 1'000 ausländische Arbeitskräfte für die NEAT rekrutieren wolle, Zweifel hätten haben sollen, solche auch hatten und diese überdies gegenüber Z._ und dem Beschwerdeführer äusserten. Wie das Strafgericht eingehend darlegte, wurden jegliche Zweifel der Ehegatten A._ systematisch mit immer neuen Lügen, gefälschten Dokumenten und letztlich gar mit dem inszenierten Treffen mit Peter Hüsy ausgeräumt. Unter diesen Umständen kann diesen nicht vorgeworfen werden, sie hätten den Irrtum mit einem Mindestmass an Aufmerksamkeit verhindern können. Unerheblich ist, dass sich die Ehegatten aus dem Vorhaben ebenfalls einen finanziellen Vorteil erhofften. Nicht erstellt ist, dass sie aus Habgier leichtgläubig handelten.
5.4 Was der Täter wusste, wollte und in Kauf nahm, betrifft so genannte innere Tatsachen (<ref-ruling> E. 2.3.2; <ref-ruling> E. 3c S. 252, mit Hinweisen), welche vor Bundesgericht nur gerügt werden können, wenn sie offensichtlich unrichtig und damit willkürlich sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (<ref-law>; <ref-ruling> E. 1.4.1). Der Beschwerdeführer profitierte auch finanziell vom Betrug, da er ebenfalls Zugriff auf die Konten der V._ Ltd. und der W._ Ltd. hatte und davon auch Geld abhob. Er legt nicht dar, weshalb die Feststellung, er habe in der Absicht gehandelt, sich und Z._ unrechtmässig zu bereichern, willkürlich sein soll.
Die Verurteilung des Beschwerdeführers wegen Betrugs verletzt kein Bundesrecht.
6. Der Beschwerdeführer sieht auch <ref-law> verletzt. Er habe nicht gewusst, woher das Geld stamme, welches auf das bereits seit 1997 bestehende Konto der V._ Ltd. floss. Mangels einer Straftat liege keine Geldwäscherei vor (Beschwerde Ziff. 19 S. 15). Damit erfüllt er die Begründungsanforderungen von Art. 42 Abs. 2 und <ref-law> nicht. Der Beschwerdeführer hat im Übrigen die Verletzung von <ref-law> vor der Vorinstanz nicht gerügt. Auf die Rüge ist nicht einzutreten.
7. 7.1 Der Beschwerdeführer wendet sich gegen die Strafzumessung. Sein Tatbeitrag sei von untergeordneter Bedeutung gewesen, was strafmildernd zu berücksichtigen sei. Auch belaufe sich der Deliktsbetrag auf weniger als Fr. 300'000.--. Da die Geschehnisse in Tunesien nicht von ihm zu verantworten seien, könne nicht von einem schweren Verschulden gesprochen werden (Beschwerde S. 17 Ziff. 23).
7.2 Die Vorinstanz erwägt mit Verweis auf das erstinstanzliche Urteil, das Verschulden des Beschwerdeführers wiege schwer. Die Tatsache, dass er vorwiegend im Hintergrund tätig gewesen sei, könne ihm nicht zugute gehalten werden, da er und Z._ arbeitsteilig vorgingen. Der Beschwerdeführer habe keinerlei Einsicht und Reue gezeigt. Er sei mehrfach einschlägig vorbestraft und habe bereits einen Teil seiner Vorstrafen verbüsst, was ihn offensichtlich unbeeindruckt gelassen habe. Nicht strafmindernd zu berücksichtigen sei, dass der angerichtete Schaden nicht übermässig hoch sei, da die voraussehbaren psychischen Auswirkungen für das Ehepaar A._ ganz aussergewöhnlich gewesen seien.
7.3 Bei der Bemessung der Strafe hat der Richter einerseits die Tatkomponenten und andererseits die Täterkomponenten zu berücksichtigen. Zu den Tatkomponenten gehören etwa das Ausmass des verschuldeten Erfolgs, die Art und Weise von dessen Herbeiführung sowie die Willensrichtung und die Beweggründe des Täters. Die Täterkomponenten umfassen unter anderem das Vorleben und die persönlichen Verhältnisse sowie das Verhalten nach der Tat und im Strafverfahren, etwa Schadenersatzzahlung, Geständnis, Einsicht und Reue (<ref-ruling> nicht publ. E. 4.2; <ref-ruling> E. 6.1, je mit Hinweisen).
7.4 Es liegt im Ermessen des Sachrichters, in welchem Umfang er die verschiedenen Strafzumessungsfaktoren berücksichtigt. Die Strafrechtliche Abteilung des Bundesgerichts greift auf Beschwerde in Strafsachen hin nur ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschritten hat, wenn sie von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wesentliche Gesichtspunkte ausser Acht gelassen beziehungsweise durch Überschreitung oder Missbrauch ihres Ermessens falsch gewichtet hat (<ref-ruling> E. 2.1; <ref-ruling> E. 6.1; <ref-ruling> E. 2).
7.5 Der Beschwerdeführer war gemäss der verbindlichen Feststellung der Vorinstanz in gleichem Masse wie Z._ an den Betrugshandlungen beteiligt. Soweit er davon abweichend geltend macht, seine untergeordnete Tatbeteiligung sei strafmildernd zu berücksichtigen, ist auf die Rüge nicht einzutreten.
Die Vorinstanz ging angesichts der Beweggründe des Beschwerdeführers und der konkreten Tatumstände zutreffend von einem schweren Verschulden aus. Die Freiheitsstrafe von vier Jahren ist, unter Berücksichtigung der einschlägigen Vorstrafen und der fehlenden Einsicht und Reue des Beschwerdeführers, nicht unangemessen hoch. Auch wenn es sich beim Betrug um eine Straftat gegen das Vermögen handelt, so sind nebst der Höhe des Schadens bei der Strafzumessung auch die übrigen Tatumstände zu berücksichtigen. Dass die Ehegatten A._ Probleme mit den tunesischen Behörden erhalten werden und dass es allenfalls zu einer Verhaftung kommen kann, war für den Beschwerdeführer voraussehbar. Nicht bundesrechtswidrig ist es, diesen Umstand, welcher von einem besonders rücksichtslosen Vorgehen zeugt, bei der Strafzumessung mitzuberücksichtigen. Die Vorinstanz hat ihr Ermessen nicht überschritten. Die Rüge ist unbegründet.
8. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist infolge Aussichtslosigkeit der Beschwerde abzuweisen (Art. 64 Abs. 1 und 2 BGG). Der finanziellen Lage des Beschwerdeführers ist bei der Festsetzung der Gerichtskosten Rechnung zu tragen (<ref-law>).

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