Sachverhalt:
A. Am 31. Oktober 2008 beantragten C._ und E._ (Beschwerdegegnerinnen) dem Kantonsgericht Schaffhausen, es seien A._ und B._ (Beschwerdeführer) aus der Liegenschaft F._ auszuweisen. Mit Verfügung vom 7. November 2008 überwies der Präsident der kantonalen Schlichtungsstelle für Mietsachen das dort am 16. September 2008 anhängig gemachte Verfahren betreffend Kündigungsanfechtung an die für das Ausweisungsbegehren zuständige Einzelrichterin des Kantonsgerichts.
Mit Verfügung vom 22. Januar 2009 wies die Einzelrichterin die Kündigungsanfechtung ab und befahl den Beschwerdeführern unter Androhung des polizeilichen Zwangsvollzugs, die von ihnen bewohnte 3 1⁄2 Zimmer-Wohnung im Dachgeschoss der Liegenschaft F._ unverzüglich zu räumen, in ordnungsgemässem Zustand zu verlassen und sämtliche zugehörigen Schlüssel herauszugeben.
B. Gegen diese Ausweisungsverfügung legten die Beschwerdeführer beim Obergericht des Kantons Schaffhausen Rekurs ein mit den Anträgen, es sei die Ausweisungsverfügung aufzuheben, dem Rekurs die aufschiebende Wirkung zu erteilen und ihnen eine Nachfrist für eine Ergänzung der Rekursbegründung anzusetzen. Mit Verfügung vom 29. Januar 2009 wies das Obergericht das Gesuch um Erteilung der aufschiebenden Wirkung sowie einer Nachfristansetzung für ergänzende Begründungen ab. Es kam zum Schluss, dass der Rekurs zum Vornherein keine ernsthaften Erfolgsaussichten habe. Die Rechtmässigkeit der Kündigung wegen Zahlungsrückstandes könne kaum in Frage gestellt werden; wenig plausibel sei namentlich die Behauptung der Beschwerdeführer, dass die ausstehenden Mietzinse durch Verrechnung mit Forderungen getilgt worden seien, die den Beschwerdeführern gegen die Vermieterschaft aus Unterhaltsarbeiten am Mietobjekt angeblich zustünden.
C. Mit Beschwerde in Zivilsachen vom 2. Februar 2009 beantragen die Beschwerdeführer dem Bundesgericht, es sei die Verfügung des Obergerichts aufzuheben und dem Rekurs vor Obergericht die aufschiebende Wirkung zu erteilen. Mit Eingabe vom 17. Februar 2009 ersuchen die Beschwerdeführer zudem um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren.
Die Beschwerdegegnerinnen schliessen in ihrer Vernehmlassung auf Abweisung der Beschwerde, sofern auf sie einzutreten sei. Die Vorinstanz verzichtet auf eine Vernehmlassung.
D. Mit Verfügung vom 3. Februar 2009 erteilte das Bundesgericht der Beschwerde superprovisorisch die aufschiebende Wirkung.

Erwägungen:
1. Mit vorliegendem Entscheid wird das Gesuch um aufschiebende Wirkung gegenstandslos.
2. Die Beschwerde in Zivilsachen ist grundsätzlich nur gegen Endentscheide im Sinne von <ref-law> zulässig, d.h. gegen Entscheide, die das Verfahren abschliessen.
2.1 Der selbständig eröffnete Entscheid über die aufschiebende Wirkung stellt einen Zwischenentscheid über eine vorsorgliche Massnahme prozessualer Natur dar (<ref-law>; vgl. <ref-ruling> E. 3.1 S. 86 f.). Dagegen ist die Beschwerde allerdings nur zulässig, wenn sie einen nicht wieder gutzumachenden Nachteil bewirken können (<ref-law>). Dabei muss es sich um einen Nachteil rechtlicher Natur handeln, der auch durch einen für den Beschwerdeführer günstigen Entscheid in der Zukunft nicht mehr behoben werden kann (<ref-ruling> E. 2.1 S. 190; <ref-ruling> E. 3.1 S. 87; je mit Hinweisen).
2.2 Die Weigerung, dem Rekurs gegen eine vollstreckbare Ausweisungsverfügung die aufschiebende Wirkung zu erteilen, bewirkt einen nicht wieder gutzumachenden Nachteil rechtlicher Natur, denn mit der Ausweisung aus der gemieteten Wohnung würde den Beschwerdeführern das Recht zum Gebrauch der Mietsache (<ref-law>) bis zur Fällung des ihnen eventuell günstigen Endentscheides genommen. Die Beschwerde in Zivilsachen steht gegen den angefochtenen Entscheid somit grundsätzlich offen.
2.3 Mit der Beschwerde gegen Entscheide über vorsorgliche Massnahmen kann nur die Verletzung verfassungsmässiger Rechte gerügt werden (<ref-law>). Soweit die Beschwerdeführer die Verletzung von kantonalem Recht oder einfachem Bundesrecht rügen, sind sie nicht zu hören. Die Verletzung von Grundrechten prüft das Bundesgericht zudem nur insofern, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Das bedeutet, dass klar und anhand der Erwägungen des angefochtenen Entscheids detailliert darzulegen ist, inwiefern verfassungsmässige Rechte verletzt worden sein sollen (<ref-ruling> E. 3.2 S. 88 mit Hinweisen).
3. Die Beschwerdeführer werfen der Vorinstanz vor, sie habe Art. 29 Abs. 1 und 2 BV, <ref-law> und Art. 6 EMRK verletzt, indem sie die offerierten Beweise betreffend die Verrechnungseinrede nicht abgenommen habe.
3.1 Nach der Rechtsprechung des Bundesgerichts umfasst der in <ref-law> gewährleistete Anspruch auf rechtliches Gehör für die entscheidende Behörde die Pflicht, die ihr rechtzeitig und formgültig angebotenen Beweismittel abzunehmen, es sei denn, diese beträfen eine nicht erhebliche Tatsache oder seien offensichtlich untauglich, die streitige Tatsache zu beweisen (<ref-ruling> E. 3 S. 157; <ref-ruling> E. 2 S. 242; <ref-ruling> E. 4a S. 469; je mit Hinweisen). Die Behörde kann auf ein beantragtes Beweismittel verzichten, wenn sie ohne Willkür in vorweggenommener Beweiswürdigung annehmen durfte, eine weitere Beweiserhebung würde ihre Überzeugung nicht beeinflussen (<ref-ruling> E. 2.1 S. 429; <ref-ruling> E. 4.2; <ref-ruling> E. 4a S. 211; je mit Hinweisen). Der Gehörsanspruch ist jedoch verletzt, wenn einem Beweismittel zum vornherein jede Erheblichkeit abgesprochen wird, ohne dass hierfür sachliche Gründe angegeben werden können (<ref-ruling> E. 2a S. 291). Ob die kantonalen Instanzen diese Grundsätze verletzt haben, prüft das Bundesgericht nur unter dem Gesichtswinkel der Willkür, da insoweit nicht der Umfang des bundesrechtlichen Anspruchs auf rechtliches Gehör, sondern lediglich eine Frage der Beweiswürdigung zu beurteilen ist (<ref-ruling> E. 3 S. 157; <ref-ruling> E. 5b/bb S. 505; <ref-ruling> E. 4c S. 269).
3.2 Die Beschwerdeführer begnügen sich damit, die der Vorinstanz offerierten Beweismittel aufzuzählen. Dass deren Nichtberücksichtigung durch die Vorinstanz willkürlich sein soll, legen die Beschwerdeführer mit keinem Wort dar. Gänzlich unbegründet bleibt auch der Vorwurf, die Vorinstanz habe <ref-law> bzw. Art. 6 EMRK verletzt. Auf diese Rügen ist somit nicht einzutreten.
4. Ebenfalls nicht zu hören sind die Rügen der Beschwerdeführer, dass C._ und E._ nicht legitimiert seien, die Ausweisung zu verlangen, und dass die Kündigung nicht formgerecht zugestellt worden sei. Diese Rügen beschlagen nicht die Verletzung verfassungsmässiger Rechte, sondern von einfachem Bundesrecht.
5. Nach dem Gesagten ist auf die Beschwerde nicht einzutreten. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kosten- und entschädigungspflichtig (<ref-law>). Aus den vorstehenden Erwägungen ergibt sich, dass die gestellten Rechtsbegehren von Beginn an keinen Erfolg haben konnten. Dem Gesuch um unentgeltliche Rechtspflege kann deshalb nicht entsprochen werden (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden den Beschwerdeführern (unter solidarischer Haftbarkeit und intern zu gleichen Teilen) auferlegt.
4. Die Beschwerdeführer haben die Beschwerdegegnerinnen für das bundesgerichtliche Verfahren (unter solidarischer Haftbarkeit und intern zu gleichen Teilen) mit Fr. 2'500.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 12. März 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Hurni