Sachverhalt:
A. Am 9. September 2008 erklärte das Strafgericht Basel-Stadt X._ der qualifizierten Widerhandlung gegen das Betäubungsmittelgesetz, der versuchten Geldwäscherei, der mehrfachen einfachen Widerhandlung gegen das Betäubungsmittelgesetz und der Hinderung einer Amtshandlung schuldig und verurteilte ihn zu einer Freiheitsstrafe von vier Jahren.
Gegen diesen Entscheid erhob X._ Appellation an das Appellationsgericht des Kantons Basel-Stadt. Am 19. August 2009 bestätigte dieses das erstinstanzliche Urteil.
B. X._ führt Beschwerde in Strafsachen beim Bundesgericht. Er beantragt, das Urteil des Appellationsgerichts des Kantons Basel-Stadt sei aufzuheben, und er sei freizusprechen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen, und diese sei gestützt auf <ref-law> anzuweisen, die rückwirkend erhobenen Randdaten der Mobiltelefonnummer xxx xxx xx xx vom 3. November 2006 bis 3. April 2007 sowie sämtliche Erkenntnisse und Folgebeweise, die auf die Erhebung dieser rückwirkenden Randdaten zurückzuführen seien, aus den Akten zu entfernen.
Der Beschwerdeführer stellt ausserdem das Gesuch um Gewährung der unentgeltlichen Prozessführung und Verbeiständung. Zudem sei ihm für das bundesgerichtliche Verfahren zu Lasten der Vorinstanz eine Parteientschädigung zuzusprechen.
C. Die Staatsanwaltschaft des Kantons Basel-Stadt beantragt die kostenfällige Abweisung der Beschwerde. Die Vorinstanz beantragt die Abweisung der Beschwerde, soweit auf diese einzutreten sei.

Erwägungen:
1. Die Vorinstanz geht von folgendem Sachverhalt aus:
Am 1. April 2007 landete A._ auf dem Flughafen Genf. Da die Kontrollbeamten in dessen Koffer Betäubungsmittel vermuteten, liessen sie ihn observieren. Er reiste mit dem Zug nach Basel weiter und rief die ihm nicht bekannte Kontaktperson "WI" auf die Nr. xxx xxx xx xx an, um Zeit- und Treffpunkt der Drogenübergabe zu erfahren. Da die Kriminalbeamten des Betäubungsmitteldezernats Basel-Stadt befürchteten, A._ werde ein Mehrfamilienhaus betreten und entschwinden, nahmen sie ihn fest, bevor es zur Übergabe kam. "WI" seinerseits konnte in der Folge nicht verhaftet werden. Im Koffer von A._ befanden sich 5'015,2 g Kokain mit einem Reinheitsgrad von 75 %.
Am 19. Februar 2008 rief eine unbekannte Person die Polizei an und teilte mit, in der Wohnung des Beschwerdeführers befänden sich 2 kg Kokain und Fr. 100'000.--. Der hierauf festgenommene Beschwerdeführer, dem die Ermittlungsbehörden im Laufe des Verfahrens die Benutzung der Mobiltelefonnummer xxx xxx xx xx zuordneten, trug bei seiner Anhaltung Fr. 7'070.-- und EUR 1'380.-- auf sich, ferner führte er vier Mobiltelefone mit sich. In der Wohnung konnten weder Kokain noch die Fr. 100'000.-- sichergestellt werden, jedoch Gepäckstücke, Bargeld, Kleider und weitere Effekten des Beschwerdeführers, die mit Kokain kontaminiert waren. Diese Effekten enthielten unter anderem einen Schlüssel für die Wohnung von B._ in Basel. In deren Wohnung, die gleichentags durchsucht wurde, fand sich ein mit Kokain kontaminierter Koffer, den der Beschwerdeführer in die Wohnung gebracht hatte.
2. 2.1 Der Beschwerdeführer rügt, die Vorinstanz habe gegen die Unschuldsvermutung gemäss <ref-law> bzw. Art. 6 Ziff. 1 EMRK verstossen, indem sie von einer geschlossenen Indizienkette ausgegangen sei, obwohl bei objektiver Würdigung der gesamten Umstände offensichtlich erhebliche, nicht zu unterdrückende Zweifel an der Glaubwürdigkeit der Zeugin B._ bestünden. Zudem habe die Vorinstanz die Aussagen der Zeugin belastend und nicht entlastend gewertet.
2.2 Die Vorinstanz führt aus, B._ habe zwar widersprüchlich ausgesagt. Die Widersprüche würden sich jedoch nur auf die Intensität der sexuellen Beziehung mit dem Beschwerdeführer beziehen. Diese könne jedoch offen bleiben, da es nicht entscheidend sei, ob er Sex mit ihr gehabt habe. Von Bedeutung sei, ob er im fraglichen Zeitraum Benutzer der Nr. xxx xxx xx xx gewesen sei. Ihre konstanten Aussagen bezüglich Benutzung der Telefonnummer habe sie erst nach einem Gespräch mit der Ehefrau des Beschwerdeführers und nach Bekanntwerden der Bedeutung dieser Telefonnummer im laufenden Verfahren geändert, weshalb diese Kehrtwende als unglaubhaft einzustufen sei.
2.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Die Feststellung des Sachverhalts durch die Vorinstanz kann nur gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich im Sinne von <ref-law> ist (<ref-ruling> E. 1.2.2), oder wenn sie auf einer Verletzung von schweizerischem Recht im Sinne von <ref-law> beruht (<ref-law>). Die Rüge der offensichtlich unrichtigen Feststellung des Sachverhalts prüft das Bundesgericht nach <ref-law> nur insoweit, als in der Beschwerde explizit vorgebracht und substantiiert dargelegt wird, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.4.3 mit Hinweisen).
2.4 Der Beschwerdeführer macht eine Verletzung der Unschuldsvermutung geltend, beruft sich zu deren Begründung jedoch ausschliesslich auf unrichtige Sachverhaltsfeststellungen der Vorinstanz, die lediglich der beschränkten Willkürprüfung unterstehen.
Was der Beschwerdeführer gegen die tatsächlichen Feststellungen der Vorinstanz einwendet, erschöpft sich in einer blossen appellatorischen Kritik am angefochtenen Urteil, die für die Begründung einer willkürlichen Feststellung des Sachverhalts nicht genügt. Die Ausführungen des Beschwerdeführers sind nicht geeignet, offensichtlich erhebliche und nicht zu unterdrückende Zweifel an der vorinstanzlichen Sachverhaltsfeststellung darzutun. Er zeigt nicht auf, inwiefern B._ generell unglaubhaft ausgesagt haben soll und deshalb, wie von ihm geltend gemacht, nicht auf ihre Aussagen abgestellt werden sollte.
3. 3.1 Der Beschwerdeführer macht geltend, die Vorinstanz habe das Bundesgesetz betreffend die Überwachung des Post- und Fernmeldeverkehrs (BÜPF) verletzt, indem sie nicht von einer bundesrechtswidrigen Randdatenerhebung der Staatsanwaltschaft ausgegangen sei. Konkret habe die Staatsanwaltschaft am 2. April 2007 verfügt, rückwirkend die Daten der Nr. xxx xxx xx xx zu erheben, wobei sie als Zielperson "UNBEKANNT" angegeben habe. Im Genehmigungsentscheid im Strafverfahren gegen A._ sei diese rückwirkende Erhebung genehmigt worden. Weder habe im Zeitpunkt der Anordnung der Randdatenerhebung noch bei deren Genehmigung gegen ihn (den Beschwerdeführer) ein Tatverdacht bestanden. Dies sei höchstens gegenüber der Person, die am 1. April 2007 das Mobiltelefon mit der Nr. xxx xxx xx xx genutzt habe, der Fall gewesen. Die Anordnung habe sich jedoch gegen eine Vielzahl möglicher Nutzer gerichtet. Das Auffinden von ihm als bisher unbekannten Dritten stelle einen Zufallsfund dar. Vor Einleitung weiterer Ermittlungen hätte die Zustimmung der Genehmigungsbehörde eingeholt werden müssen (Beschwerde, S. 7 ff.).
3.2 Die Vorinstanz erwägt, die Behörden hätten aufgrund der Aussage von A._ vom 1. April 2007 gewusst, dass der Abnehmer des transportierten Kokains die Nr. xxx xxx xx xx benutzt. Nur die Identität des Abnehmers sei damals noch nicht bekannt gewesen. Im Überwachungsantrag sei A._ als Person 1 bezeichnet worden, der unbekannte Abnehmer als Person 2. Der Antrag erfülle die Anforderungen an eine Überwachung gemäss BÜPF. Es treffe daher nicht zu, dass die Erkenntnisse aus der Erhebung der rückwirkenden Randdaten der Nr. xxx xxx xx xx eine Person betroffen hätten, die in der Genehmigungsverfügung vom 3. April 2007 keiner Straftat verdächtigt worden wäre. Die Genehmigung sei im Wissen darum erteilt worden, was mit der rückwirkenden Randdatenerhebung bezweckt werden sollte. Im Weiteren habe die Haftrichterin am 14. März 2008 die rückwirkende Erhebung der Randdaten vom 14. September 2007 bis zum 14. März 2008 im Strafverfahren gegen den Beschwerdeführer in Kenntnis der früheren Datenerhebung genehmigt.
3.3 <ref-law> mit der Marginalie "Zufallsfunde" statuiert, dass bezüglich Ermittlungserkenntnissen, welche Straftaten einer Person betreffen, die in der Überwachungsanordnung keiner Straftat verdächtigt wird, vor Einleitung weiterer Ermittlungen die Zustimmung der Genehmigungsbehörde eingeholt werden muss (Abs. 2 Satz 1). Die Zustimmung kann erteilt werden, wenn die Voraussetzungen für eine Überwachung nach diesem Gesetz erfüllt sind (Abs. 2 Satz 2). Sind die Voraussetzungen für die Verwendung des Zufallsfundes nicht gegeben, so dürfen die Informationen nicht verwendet, und es müssen die betreffenden Dokumente und Datenträger umgehend vernichtet werden (Abs. 3). Für die Fahndung nach gesuchten Personen dürfen sämtliche Erkenntnisse einer Überwachung verwendet werden (Abs. 4).
3.4 Ein sogenannter personeller Zufallsfund im Sinne von <ref-law> liegt entgegen der Ansicht des Beschwerdeführers und im Einklang mit der Vorinstanz im zu beurteilenden Fall nicht vor. Die Untersuchungsbehörden wurden auf den Beschwerdeführer als möglichen Drogenlieferanten von A._ nicht erst aufmerksam, weil dessen Telefonanschluss rechtmässig überwacht worden war (so die Konstellation in <ref-ruling>, wo das Bundesgericht einen personellen Zufallsfund bejahte). Vielmehr bestand der Tatverdacht, weil A._ in Untersuchungshaft verraten hatte, sein Abnehmer des von ihm transportierten Kokains benutze die Nr. xxx xxx xx xx. Vor der Überwachung war somit einzig die Identität des Abnehmers nicht bekannt. Die Vorinstanz verletzt daher kein Bundesrecht, wenn sie einen personellen Zufallsfund verneint. Entsprechend war sie auch nicht gehalten, zur Verwendung der Randdaten gegen den Beschwerdeführer eine (erneute) Zustimmung der Genehmigungsbehörde zu verlangen.
4. 4.1 Der Beschwerdeführer macht eine Verletzung des rechtlichen Gehörs (Art. 29 Abs. 2, <ref-law> und Art. 6 Ziff. 3 lit. d EMRK) geltend. Die Vorinstanz habe zu Unrecht auf die Einholung sämtlicher Randdaten bei der Staatsanwaltschaft verzichtet. Er habe bereits im Vorfeld der zweitinstanzlichen Verhandlung im Sinne eines Eventualantrags vorgebracht, falls eine Entfernung der Randdaten aus den Akten abgelehnt werde, die gesamten Randdaten auszulesen und ihm zur Verfügung zu stellen. Diesen Antrag habe die Vorinstanz vor Abschluss des Beweisverfahrens nicht behandelt. Die Nichtbehandlung eines rechtzeitig eingereichten Beweisantrags verletze den Anspruch auf rechtliches Gehör.
4.2 Die Vorinstanz erwägt, der Beschwerdeführer habe in der Hauptverhandlung sämtliche vorgängig gestellten Anträge wiederholt und einlässlich begründet, nicht jedoch den Eventualantrag. Es sei deshalb davon auszugehen gewesen, er halte an diesem Eventualantrag nicht fest. Im Übrigen habe sie sich (wie auch die erste Instanz) nur auf diejenigen Randdaten abgestützt, die in den Akten zu finden seien.
4.3 <ref-law> gewährleistet den Anspruch auf rechtliches Gehör. Daraus ergibt sich der Anspruch der Parteien, mit rechtzeitig und formgültig angebotenen Beweisanträgen und Vorbringen gehört zu werden, soweit diese erhebliche Tatsachen betreffen und nicht offensichtlich beweisuntauglich sind (<ref-ruling> E. 2.1 mit Hinweisen). <ref-law> räumt jeder angeklagten Person den Anspruch darauf ein, möglichst rasch und umfassend über die gegen sie erhobenen Beschuldigungen unterrichtet zu werden. Sie muss die Möglichkeit haben, die ihr zustehenden Verteidigungsrechte wahrzunehmen.
4.4 Der Beschwerdeführer hat am 17. August 2009 in seinem Schreiben an die Vorinstanz einen (Eventual-) Antrag auf Herausgabe der erhobenen Randdaten der Nr. xxx xxx xx xx gestellt (pag. 1634 der Vorakten). Dieser Antrag wurde gültig gestellt und bedurfte daher keiner Wiederholung anlässlich der vorinstanzlichen Hauptverhandlung. Der Auffassung der Vorinstanz, es liege ein stillschweigender Verzicht auf diesen Antrag vor, kann nicht gefolgt werden. Der Beschwerdeführer hätte erwarten können und dürfen, dass sich die Vorinstanz bei abgelehntem Hauptantrag auch ohne mündliche Wiederholung des Eventualantrags mit diesem befassen würde. Zumindest hätte die Vorinstanz bei Zweifeln nachfragen müssen, ob und inwieweit der Beschwerdeführer an seinen Anträgen festhalten möchte. Der Beschwerdeführer kann hieraus allerdings nichts zu seinen Gunsten ableiten.
Die Vorinstanz hat zwar die CD-Rom mit den fraglichen Randdaten dem Beschwerdeführer mit Verfügung vom 12. Oktober 2009 (Versand am 27. Oktober 2009) und somit nach der Urteilseröffnung vom 19. August 2009 zur Verfügung gestellt. Entgegen seiner Ansicht waren ihm die fallrelevanten Randdaten jedoch bereits vorher zur Kenntnis gebracht worden. Diese wurden ihm nämlich erstmals anlässlich der Einvernahme durch die Staatsanwaltschaft Basel-Stadt vom 13. März 2008 im Beisein seines ersten Verteidigers vorgelegt (pag. 834 ff. der Vorakten). In einer weiteren Einvernahme vom 6. Mai 2008 (pag. 971 ff. der Vorakten), bei dem sein zweiter Verteidiger anwesend war, wurden sie ihm erneut unterbreitet. Bei beiden Gelegenheiten hat der Beschwerdeführer mittels Unterschrift die Kenntnisnahme der Randdaten bestätigt. Er hat es ausserdem unterlassen, im Rahmen der ihm gewährten Einsichtnahme in die Verfahrensakten eine Durchsicht der in Papierform bzw. CD-Rom vorhandenen Randdaten zu verlangen. Eine Verletzung des rechtlichen Gehörs liegt damit nicht vor.
5. 5.1 Der Beschwerdeführer rügt eine Verletzung der Unschuldsvermutung, da eine Analyse der kompletten Randdaten zeige, dass er im April 2007 unmöglich der Benutzer des Mobiltelefons mit der Nr. xxx xxx xx xx gewesen sein könne. Er versucht dabei mit verschiedenen Beweismitteln aufzuzeigen, dass er sich an mehreren Daten nicht am registrierten Ort des geführten Telefonats befunden hatte.
5.2 Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der angefochtene Entscheid dazu Anlass gab (<ref-law>; <ref-ruling> E. 2.1 mit Hinweis). Da der Beschwerdeführer bereits in einem frühen Zeitpunkt des Verfahrens Kenntnis der Randdaten hatte und etwaige Widersprüche zwischen seinen verschiedenen Aufenthaltsorten und denjenigen des Benutzers des betreffenden Mobiltelefons bereits im vorinstanzlichen Verfahren hätte aufzeigen können, ist auf seine Rüge nicht einzutreten.
6. 6.1 Der Beschwerdeführer stellte im vorinstanzlichen Verfahren den Antrag, die Staatsanwaltschaft sei aufzufordern, etwaige weitere Ermittlungsakten bezüglich Ermittlungen zwischen dem 25. Juli 2007 und Februar 2008 gegen ihn vorzulegen. Die Staatsanwaltschaft verneinte die Existenz von Ermittlungsakten für diesen Zeitraum. Die Vorinstanz erklärte, dies sei "einigermassen schwer zu glauben", lasse sich aber auch nicht völlig ausschliessen. Es müsse damit gestützt auf den Grundsatz "negativa non sunt probanda" sein Bewenden haben. Der Beschwerdeführer rügt, die Vorinstanz habe dadurch gegen Art. 29 Abs. 2 sowie <ref-law> verstossen, indem sie die Ausführungen der Staatsanwaltschaft akzeptierte.
6.2 Die Rüge des Beschwerdeführers geht fehl. Eine Verletzung des rechtlichen Gehörs liegt nicht vor. Die Staatsanwaltschaft legte einlässlich dar, dass die vorhandenen Akten vollständig seien, der Ablauf des Ermittlungsverfahrens lückenlos dokumentiert sei und daher kein Raum für Spekulationen offenlasse (act. 1541 f. der Vorakten). Die Vorinstanz konnte daher, auch wenn sie gewisse Zweifel über die Richtigkeit dieser Angaben hegte, auf weitere diesbezügliche Abklärungen verzichten, ohne Bundesrecht zu verletzen.
7. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens hat der Beschwerdeführer die Kosten des Verfahrens zu tragen (<ref-law>). Das Gesuch des Beschwerdeführers um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung ist abzuweisen, da die Beschwerde von vornherein aussichtslos war. Seiner finanziellen Lage ist mit herabgesetzten 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 und Verbeiständung 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, 11. März 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Keller