Sachverhalt:
A. Die 1956 geborene O._ meldete sich am 24. April 2007 bei der Invalidenversicherung zum Leistungsbezug an. Nach Abklärungen in erwerblicher und medizinischer Hinsicht, insbesondere eines polydisziplinären Gutachtens des Begutachtungszentrums X._, vom 31. Januar 2008, stellte die IV-Stelle Basel-Stadt mit Vorbescheid vom 14. Mai 2005 die Ablehnung des Leistungsbegehrens gestützt auf einen Invaliditätsgrad von 10 % in Aussicht. Auf Einwand von O._ vom 16. Juni 2008 hin wies die IV-Stelle einen Rentenanspruch mit Verfügung vom 31. Juli 2008 ab, nunmehr basierend auf einem Invaliditätsgrad von 37 %.
B. Die hiegegen erhobene Beschwerde hiess das Sozialversicherungsgericht Basel-Stadt mit Entscheid vom 18. März 2009 teilweise gut, wies die Sache entsprechend dem vernehmlassungsweise gestellten Antrag der IV-Stelle zur Verfügung bezüglich der Höhe des Anwaltshonorars im Vorbescheidverfahren an die IV-Stelle zurück und wies die Beschwerde im Übrigen ab, nachdem diese mit ihrer Beschwerdeantwort einen ergänzenden Bericht des Begutachtungszentrums X._ vom 11. November 2008 eingereicht und das Gericht O._ am 25. November 2008 diese beiden Dokumente zugestellt hatte mit dem Hinweis "zur kurzen Replik (ohne Arztberichte) innert Frist bis 5. Januar 2009".
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt O._ beantragen, unter Aufhebung des vorinstanzlichen Entscheides im Rentenpunkt sei die Sache an die IV-Stelle zur weiteren Abklärung zurückzuweisen. Zudem ersucht sie um Gewährung der unentgeltlichen Rechtspflege.
Die IV-Stelle schliesst auf Abweisung der Beschwerde, während das Bundesamt für Sozialversicherungen (BSV) und das Sozialversicherungsgericht Basel-Stadt auf eine Vernehmlassung verzichten.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzung gemäss den Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>; vgl. auch <ref-law>; ohne Beschwerden gemäss <ref-law> und <ref-law>). Mit Blick auf diese Kognitionsregelung ist aufgrund der Vorbringen in der Beschwerde an das Bundesgericht (<ref-law>) nur zu prüfen, ob der angefochtene Gerichtsentscheid in Anwendung der massgeblichen materiell- und beweisrechtlichen Grundlagen (unter anderem) Bundesrecht verletzt (<ref-law>). Hiezu gehört insbesondere auch die unvollständige (gerichtliche) Feststellung der rechtserheblichen Tatsachen und die Verletzung des Untersuchungsgrundsatzes als einer wesentlichen Verfahrensvorschrift (Urteile 9C_534/2007 vom 27. Mai 2008, E. 1 mit Hinweis auf Ulrich Meyer, N 58-61 zu Art. 105, in: Niggli/Uebersax/Wiprächtiger [Hrsg.], Basler Kommentar Bundesgerichtsgesetz, Basel 2008; Seiler/von Werdt/Güngerich, Kommentar zum Bundesgerichtsgesetz, Bern 2007, N. 24 zu Art. 97).
2. Streitig und zu prüfen ist, ob die Beschwerdeführerin Anspruch auf eine Rente der Invalidenversicherung hat. Dabei ist vorab die formelle Rüge der Beschwerdeführerin zu prüfen, die Vorinstanz habe das rechtliche Gehör und den Grundsatz der Waffengleichheit verletzt, indem diese ihr anlässlich der Einräumung des Replikrechts verwehrt habe, weitere Arztberichte einzureichen.
2.1 Die Vorinstanz hat diesbezüglich ausgeführt, mit der Beschwerde habe die Versicherte einen Bericht des Dr. med. H._ eingereicht, auf den sie ihre Kritik am Gutachten des Begutachtungszentrums X._ abstütze. Der Bericht sei am 25. August 2008, somit nach Erlass der Verfügung vom 31. Juli 2008 verfasst worden. Dies treffe zwar auch auf den Bericht des Begutachtungszentrums X._ vom 11. November 2008 zu, der sich mit den auf den Bericht von Dr. med. H._ abgestützten Ausführungen in der Beschwerde befasse. Wäre es der Beschwerdeführerin nun unbenommen gewesen, zur Untermauerung der am 21. Januar 2009 eingereichten Replik weitere Arztberichte zu veranlassen und nachzureichen, wären angesichts der noch grösseren zeitlichen Distanz zwischen der Abfassung solcher Berichte und dem vorliegend relevanten Sachverhalt, wie er sich bei Erlass der angefochtenen Verfügung im Juli 2008 präsentiert hatte, keine neuen Erkenntnisse mehr zu erwarten gewesen. Zudem sei der Beschwerdeführerin entgegen zu halten, dass sie in der Replik nicht näher konkretisiere, welche fach- oder vertrauensärztlichen Berichte zur Widerlegung der Ausführungen des Begutachtungszentrums X._ gemäss Bericht vom 11. November 2008 hätten in Betracht fallen können. Entsprechende Beweisanträge fehlten; die Replik sehe davon ab, Namen bestimmter Fachärzte zu nennen oder auch nur die in Betracht fallende medizinische Fachrichtung solcher Ärzte anzuführen. Folglich liege in der Anordnung des Instruktionsrichters, der Replik keine weiteren Arztberichte beizulegen, kein Verstoss gegen das Gebot der Waffengleichheit.
2.2 Demgegenüber macht die Beschwerdeführerin geltend, der bereits im Abklärungsverfahren von der IV-Stelle beauftragte Dr. med. Z._ habe im umfassenden Bericht vom 11. November 2008 Punkt für Punkt zur Beschwerde Stellung genommen. Der Instruktionsrichter habe es der Beschwerdeführerin verwehrt, zu diesem neuen Bericht einen Arztbericht aufzulegen. Es sei offensichtlich, dass die Versicherte auf fachliche Hilfe angewiesen gewesen sei, um die fachlichen Ausführungen des Dr. med. Z._ zu beantworten. Das Sozialversicherungsgericht habe der IV-Stelle das Recht eingeräumt, mit der Beschwerdeantwort einen ausführlichen neuen Arztbericht einzureichen. Dasselbe Recht habe das Gericht der Beschwerdeführerin verwehrt. Der Grundsatz der Waffengleichheit sei klar verletzt. Die Vorinstanz verkenne, dass es Sache der Parteien sei, zu entscheiden, ob sie zu einer Eingabe Bemerkungen machen wollen oder nicht. Das Vertrauen in die Justiz gründe unter anderem auf der Gewissheit, sich zu jedem Aktenstück äussern zu können. Nur mit Hilfe eines Arztberichtes hätte die Beschwerdeführerin der Einschätzung des IV-Vertrauensarztes wirksam begegnen können. Es könne nicht gesagt werden, ein solcher Bericht wäre von vornherein nicht geeignet gewesen, sich auf den Ausgang des Verfahrens auszuwirken. Das weitere Argument, die Beschwerdeführerin habe im Rahmen der Replik keine Beweisanträge gestellt, sei widersprüchlich, wenn von vornherein feststehe, dass keine Arztberichte zugelassen würden. Die Vorinstanz habe die Ausführungen von Dr. med. Z._ in der Frage der Beinbeschwerden (Ziff. 3.2.1) und der Kopfschmerzen (Ziff. 3.2.2, S. 9) zur Basis ihres Urteils erhoben. Da die Beschwerdeführerin zu entscheidwesentlichen Vorbringen der Verwaltung keine eigenen Arztberichte habe einbringen können, habe die Vorinstanz den Anspruch auf rechtliches Gehör und die Waffengleichheit verletzt. Zudem sei es der IV-Stelle nach der Rechtsprechung verwehrt, auf Stufe Gericht im Verwaltungsverfahren versäumte wesentliche Sachverhaltsabklärungen nachzuholen, da dies vor Verfügungserlass geschehen müsse. Vorliegend habe die IV-Stelle die im Verwaltungsverfahren nicht abgeklärten angiologischen Beschwerden, die Kopfschmerzen, die Rücken- und Fussbeschwerden erst im Beschwerdeverfahren in den Zusammenhang der somatoformen Schmerzstörung gestellt. Diese Sachverhaltsabklärungen hätten auf Verfügungsstufe durchgeführt werden müssen.
3. 3.1 Gemäss <ref-law> haben die Parteien Anspruch auf rechtliches Gehör. Das rechtliche Gehör dient einerseits der Sachaufklärung, andererseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung einer Person eingreift, und kann im Verwaltungs- und Verwaltungsgerichtsverfahren mit den Erfordernissen eines geordneten Verfahrensganges oder der Prozessökonomie kollidieren. Dazu gehört insbesondere deren Recht, sich vor Erlass des in ihre Rechtsstellung eingreifenden Entscheids zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen (<ref-ruling> E. 3.1 S. 370 mit Hinweisen).
Der Anspruch einer Partei, im Rahmen eines Gerichtsverfahrens zu replizieren, bildet einen Teilgehalt des verfassungsmässigen Anspruchs auf rechtliches Gehör (<ref-law>). Im Anwendungsbereich von Art. 6 Ziff. 1 EMRK ist es den Gerichten nicht gestattet, einer Partei das Äusserungsrecht zu eingegangenen Stellungnahmen bzw. Vernehmlassungen der übrigen Verfahrensparteien, unteren Instanzen und weiteren Stellen abzuschneiden. Die Partei ist vom Gericht nicht nur über den Eingang dieser Eingaben zu orientieren; sie muss ausserdem die Möglichkeit zur Replik haben (<ref-ruling> E. 3.3.3 S. 47 mit Hinweisen auf die Rechtsprechung des Europäischen Gerichtshofs für Menschenrechte). <ref-law> gebietet, dass die Gerichte diesen Grundsatz auch ausserhalb von Art. 6 Ziff. 1 EMRK beachten. In diesem Sinne kommt <ref-law> und Art. 6 Ziff. 1 EMRK im Hinblick auf das Replikrecht in gerichtlichen Verfahren dieselbe Tragweite zu (<ref-ruling> E. 2.1 S. 99; vgl. <ref-ruling> E. 4.6 S. 104).
Gehen in einem Gerichtsverfahren Vernehmlassungen und Stellungnahmen von Parteien und Behörden ein, so werden diese den übrigen Verfahrensbeteiligten im Allgemeinen zur Kenntnisnahme zugestellt. Diese Zustellung kann verbunden werden mit der Anordnung eines zweiten Schriftenwechsels. Ein solcher wird jedoch nur ausnahmsweise eröffnet (vgl. für das bundesgerichtliche Verfahren: <ref-law>). Das Gericht kann aber auch eine neu eingegangene Eingabe den Parteien ohne ausdrücklichen Hinweis auf allfällige weitere Äusserungsmöglichkeiten zur (blossen) Kenntnisnahme übermitteln, was im Bereich des Sozialversicherungsrechts regelmässig der Fall ist. Schliesslich wird eine neu eingegangene Eingabe den Parteien häufig ohne ausdrücklichen Hinweis auf allfällige weitere Äusserungsmöglichkeiten zur (blossen) Kenntnisnahme übermittelt. Kommen Verfahrensbeteiligte, welche eine solche Eingabe ohne Fristansetzung erhalten haben, zum Schluss, sie möchten nochmals zur Sache Stellung nehmen, so sollen sie dies aus Gründen des Zeitgewinns tun, ohne vorher darum nachzusuchen. Nach Treu und Glauben hat dies jedoch umgehend zu erfolgen. Das Bundesgericht wartet bei der letztgenannten Vorgehensweise mit der Entscheidfällung zu, bis es annehmen darf, der Adressat habe auf eine weitere Eingabe verzichtet (<ref-ruling> E. 2.2 S. 99 f.).
3.2 Es steht fest, dass der Beschwerdeführerin das Recht zustand, sich zum Ergänzungsbericht des Begutachtungszentrums X._ zu äussern, wovon sie auch Gebrauch gemacht hat. Allerdings nahm dieser Ergänzungsbericht nicht nur ausführlich zu jedem Punkt der Beschwerde Stellung, sondern besprach zudem zur beschwerdeweise vorgetragenen Rüge, es sei keine angiologische Abklärung vorgenommen worden, einen erst nach Verfügungserlass erstellten Bericht vom 21. August 2008 von Frau Dr. med. K._ und ging damit über eine reine Erläuterung der gutachterlichen Schlussfolgerungen hinaus. Auch wurden darin erstmals die unklaren angiologischen Beschwerden und die Kopfschmerzen in den Zusammenhang der somatoformen Schmerzstörung gestellt. Ob die Beschwerdeführerin unter diesen besonderen Umständen das ihr zustehende Replikrecht, wie sie einwendet, nur mit der Einreichung eines neuen Arztberichtes hätte hinreichend wahrnehmen können, was ihr von der Vorinstanz gerade verwehrt wurde, und damit eine Verletzung des rechtlichen Gehörs vorliegt, die eine Rückweisung rechtfertigt, kann offen bleiben, da die Sache ohnehin aus materiellen Gründen an die IV-Stelle zurückzuweisen ist:
4. Wie die Beschwerdeführerin zu Recht einwendet, erweist sich der medizinische Sachverhalt angesichts der komplexen medizinischen Verhältnisse als ungenügend abgeklärt. Dies gilt einmal hinsichtlich der angiologischen Situation und daraus resultierender möglicher invalidisierender Beschwerden: Während im Rahmen des Gutachtens vom 31. Januar 2008 kein Spezialarzt für Venenleiden beigezogen wurde, dort aber die Rheumatologin Dr. med. G._ festhielt, die Beinbeschwerden seien eher eine Folge der beidseitigen chronisch-venösen Insuffizienz, wurde erst im Ergänzungsbericht zur Rüge, es sei keine angiologische Abklärung vorgenommen worden, der Bericht von Frau Dr. med. K._ vom 21. August 2008 besprochen. Danach sei angesichts der vorliegenden Venensituation eine "Sanierung" nicht zu erwarten, Rezidive seien quasi vorprogrammiert. Zusätzlich sei das Beschwerdebild sicher nur teilweise durch diese Venensituation erklärbar. Dr. med. Z._ schliesst daraus (erstmals), diese Beschwerden seien teilweise im Rahmen der somatoformen Schmerzstörung zu sehen, ohne jedoch über die entsprechende fachärztliche Qualifikation zu verfügen. Demgegenüber hatte Dr. med. von A._, Spezialarzt FMH für Psychiatrie und Psychotherapie, im psychiatrischen Teilgutachten zwar die somatoforme Schmerzstörung diagnostiziert, gleichzeitig aber auch erklärt, den somatischen Akten sei nicht klar zu entnehmen, inwieweit sich die Schmerzen hinreichend durch körperliche Störungen erklären lassen oder nicht. Damit erlaubt die Aktenlage keine zuverlässige Beurteilung, ob die Beinbeschwerden somatische Ursachen haben oder im Rahmen der somatoformen Schmerzstörung zu sehen sind. Dies gilt ebenso für die von der Beschwerdeführerin beklagten Kopfschmerzen, welche Dr. med. Z._ ebenfalls neu der somatoformen Schmerzstörung zurechnet, und welche anlässlich der Begutachtung auch nicht facharztspezifisch abgeklärt wurden. Schliesslich wurde die Frage von nachweisbaren Degenerationen der HWS, welche Dr. med. H._ in seinem Bericht vom 25. August 2008 feststellte, die im Gutachten aber nicht erwähnt wurden, nicht überzeugend ausgeräumt.
Neben den im Gutachten erhobenen Diagnosen mit Auswirkung auf die Arbeitsfähigkeit (1. chronischer Kreuz- und Nackenschmerz mit zephaler Komponente mit/bei lumbal linkskonvexer Skoliose, Hyperlordose lumbal und zervikal, Beckentiefstand links, Schulterhochstand rechts, Spondylarthrosen L2/3 - L5/S1, Chondrosen L4/5 und L5/S1, primäre und sekundäre Spinalkanalstenose; 2. Schulterschmerz linksbetont mit/bei klinischer Supraspinatus- und Subscapularisstenose links, diffuse Druckdolenz des Schultergürtels beidseits, Epicondylopathia humeri radialis rechtsbetont; 3. belastungsabhängiger Fussschmerz rechtsbetont mit/bei radiologisch unterem und oberen Fersensporn rechts; 4. anhaltende somatoforme Schmerzstörung, ICD10 F45.5) ergibt sich damit insgesamt kein vollständiges Bild der gesundheitlichen Situation der Versicherten und der ihr zumutbaren Arbeitsfähigkeit. Deshalb wäre das kantonale Gericht gehalten gewesen, weitere Abklärungen zu veranlassen (<ref-law>, Art. 43 Abs. 1 und Art. 61 lit. c ATSG; <ref-ruling> E. 5.2.5 S. 68 f.); diese unvollständige Feststellung des rechtserheblichen Sachverhaltes ist vom Bundesgericht als Rechtsverletzung zu berücksichtigen (9C_865/2007; Seiler, a.a.O., Art. 97 N 24). Die Sache ist daher an die IV-Stelle zurückzuweisen, damit sie ergänzende Abklärungen hinsichtlich der Beinverhältnisse, der Kopfschmerzen und der degenerativen Veränderungen der HWS als mögliche Ursache für die Beschwerden vornehme und anschliessend über den Rentenanspruch neu entscheide.
5. Dem Ausgang des Verfahrens entsprechend hat die Beschwerdegegnerin die Gerichtskosten zu tragen (<ref-law>) und der Beschwerdeführerin eine Parteientschädigung zu bezahlen (<ref-law>). Das Gesuch um unentgeltliche Rechtspflege ist gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der Entscheid des Sozialversicherungsgerichts des Kantons Basel-Stadt vom 18. März 2009 und die Verfügung der IV-Stelle Basel-Stadt vom 31. Juli 2008 werden aufgehoben. Die Sache wird an die IV-Stelle zurückgewiesen, damit sie, nach erfolgter Abklärung im Sinne der Erwägungen, über den Anspruch auf eine Invalidenrente neu verfüge.
2. Die Gerichtskosten von Fr. 500.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat die Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4. Die Sache wird zur Neuverlegung der Kosten und der Parteientschädigung des vorangegangenen Verfahrens an das Sozialversicherungsgericht des Kantons Basel-Stadt zurückgewiesen.
5. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht Basel-Stadt und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 22. Juni 2010
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Helfenstein Franke