Sachverhalt:
A. Am 31. Oktober 2008 beantragten F.H._ und J.K.-H._ (Beschwerdegegnerinnen) dem Kantonsgericht Schaffhausen, es seien A.E._ und B.E._ (Beschwerdeführer) aus der Liegenschaft X._ 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 Schaffhausen. 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 X._ unverzüglich zu räumen, in ordnungsgemässem Zustand zu verlassen und sämtliche zugehörigen Schlüssel herauszugeben.
B. Dagegen erhoben die Beschwerdeführer beim Obergericht des Kantons Schaffhausen Rekurs und beantragten im Wesentlichen, die Begehren der Beschwerdegegnerinnen vollumfänglich abzuweisen. Es sei festzustellen, dass die Kündigung vom 16. September 2008 nichtig sei und demzufolge keine Rechtswirkung entfalte. Eventualiter sei die Kündigung als ungültig aufzuheben, wobei festzustellen sei:
dass den Beschwerdeführern gegenüber den Beschwerdegegnerinnen aus Malerarbeiten am Mietobjekt eine Forderung zusteht, welche die Mietzinse für die Monate November 2007 bis und mit Juli 2008 à Fr. 800.--, d.h. total Fr. 7'200.-- übersteigt;
dass die Beschwerdeführer zur Tilgung der Mietzinse für die Zeit von November 2007 bis und mit Juli 2008 frist- und formgerecht die Verrechnungseinrede erhoben haben;
sich die Beschwerdeführer demgemäss bezüglich der Leistung der von den Beschwerdegegnerinnen abgemahnten Mietzinse nicht in Verzug befinden.
Subeventualiter sei die Kündigung in Anwendung von Art. 271/271a Abs. 1 lit. a OR als ungültig aufzuheben. Sub-subeventualiter sei das Mietverhältnis in Anwendung von <ref-law> für die Dauer von vier Jahren zu erstrecken.
Mit Verfügung vom 29. Januar 2009 wies der Präsident des Obergerichts das Gesuch der Beschwerdeführer, dem Rekurs die aufschiebende Wirkung zu erteilen und ihnen eine Nachfrist für eine Ergänzung der Rekursbegründung anzusetzen, ab. Auf eine dagegen erhobene Beschwerde in Zivilsachen trat das Bundesgericht mit Urteil vom 12. März 2009 nicht ein (4A_64/2009).
Am 9. April 2009 wies das Obergericht den Rekurs ab.
C. Die Beschwerdeführer beantragen mit Beschwerde in Zivilsachen, diesen Entscheid des Obergerichts vollumfänglich aufzuheben, das Ausweisungsbegehren vollumfänglich abzuweisen und die angefochtene Wohnungskündigung als ungültig aufzuheben. Ausserdem erneuern sie als "Unteranträge" ihre im obergerichtlichen Verfahren gestellten Feststellungsbegehren.
Mit Eingabe vom 5. Mai 2009 ersuchen die Beschwerdeführer zudem um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren.
Die Beschwerdegegnerinnen schliessen auf Abweisung der Beschwerde, sofern auf sie einzutreten sei. Die Vorinstanz verzichtete auf eine Vernehmlassung.
D. Mit Verfügung vom 20. April 2009 wurde der Beschwerde superprovisorisch die aufschiebende Wirkung erteilt.

Erwägungen:
1. Mit dem vorliegenden Entscheid in der Sache selbst wird das Gesuch um aufschiebende Wirkung gegenstandslos.
2. Der angefochtene Entscheid des Obergerichts ist ein verfahrensabschliessender Endentscheid (<ref-law>) einer letzten kantonalen Instanz (<ref-law>). Sodann übersteigt der Streitwert bei einem monatlichen Mietzins von Fr. 800.-- die Grenze nach <ref-law> (vgl. <ref-law> und Urteil 4A_148/2008 vom 18. April 2008 E. 1; <ref-ruling> E. 1, je mit Hinweisen). Auf die Beschwerde kann grundsätzlich eingetreten werden. Dies gilt allerdings von vornherein nicht bezüglich der Feststellungsbegehren, da dieselben lediglich die Feststellung von Vorfragen zum Gegenstand haben, die im Rahmen der Beurteilung der Gültigkeit der Kündigung zu prüfen sind und keinen selbständigen Charakter haben.
3. Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, andernfalls wird darauf nicht eingetreten. In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Unbeachtlich sind blosse Verweise auf die Akten; inwiefern das angefochtene Urteil Bundesrecht verletzt, ist in der Beschwerdeschrift selber darzulegen (vgl. <ref-ruling> E. 3.1 S. 400; <ref-ruling> E. 1d; <ref-ruling> E. 2; <ref-ruling> E. 3 S. 85). Soweit die Beschwerdeführer auf die Ausführungen in ihren kantonalen Rechtsschriften verweisen, kann darauf von vornherein nicht eingegangen werden.
4. Ist der Mieter nach der Übernahme der Sache mit der Zahlung fälliger Mietzinse oder Nebenkosten im Rückstand, so kann ihm der Vermieter nach <ref-law> schriftlich eine Zahlungsfrist setzen und ihm androhen, dass bei unbenütztem Ablauf der Frist das Mietverhältnis gekündigt werde. Diese Frist beträgt bei Wohn- und Geschäftsräumen mindestens 30 Tage. Bezahlt der Mieter innert der gesetzten Frist nicht, so kann der Vermieter fristlos, bei Wohn- und Geschäftsräumen mit einer Frist von mindestens 30 Tagen auf Ende eines Monats kündigen (<ref-law>).
4.1 Die Vorinstanz (wie schon die Erstinstanz) hat den Zahlungsrückstand der Beschwerdeführer bejaht und demzufolge die Kündigung für gültig und die Ausweisung für berechtigt beurteilt. Die Beschwerdeführer rügen die Verletzung von <ref-law>/SH, <ref-law> i.V.m. <ref-law>, <ref-law>, <ref-law>, <ref-law>, <ref-law> und Art. 6 EMRK. Die geltend gemachten Rechtsverletzungen erblicken sie darin, dass die Vorinstanz die "Einrede der Tilgung der abgemahnten Mietzinse zufolge Verrechnung mit einer Ersatzforderung für geleistete Unterhaltsarbeiten bzw. Mängelbehebung ignoriert" habe. Insbesondere rügen sie eine willkürliche antizipierte Beweiswürdigung bzw. eine den Anspruch auf rechtliches Gehör verletzende Zurückweisung von angebotenen Beweisen.
4.2 Die Vorinstanz hielt den Bestand der von den Beschwerdeführern zur Verrechnung gebrachten Forderung für nicht erstellt. Sie vermisste bereits eine hinreichende Substantiierung. So hätten die Beschwerdeführer lediglich pauschal geltend gemacht, dass sie "umfassende Malerarbeiten" ausgeführt hätten und dass F.H._ mit der Restaurierung aller Decken einverstanden gewesen sei. Da aus den Vorbringen der Beschwerdeführer sowie aus den Akten nicht hervorgehe, welche Arbeiten sie konkret ausgeführt haben wollen, könnte darüber zum Vornherein kein Beweis abgenommen werden.
Diese Begründung fechten die Beschwerdeführer nicht an. Im Gegenteil führen sie in ihrer Beschwerde - missverständlich - aus, nach zutreffender Auffassung der Vorinstanzen hätten die Beschwerdeführer die Verrechnungseinrede rechtzeitig und hinlänglich substantiiert erhoben. Sie übergehen den Vorwurf der mangelnden Substantiierung und lassen ihn unangefochten. Fehlt es aber an hinreichend substantiierten Behauptungen, kann nicht Beweis geführt werden und der Vorwurf der Nichtabnahme angebotener Beweise stösst ins Leere (vgl. <ref-ruling> E. 2.6; <ref-ruling> E. 2b).
4.3 Die Vorinstanz hat in einer Eventualbegründung erwogen, selbst wenn die allfälligen Leistungen der Beschwerdeführer zum Beweis verstellt werden müssten, wäre aufgrund einer antizipierten Beweiswürdigung anzunehmen, dass den Beschwerdeführern der Beweis nicht gelingen würde. So sei die offerierte persönliche Befragung der Beschwerdeführer unzulässig bzw. jedenfalls von geringem Beweiswert, da absehbar sei, dass sie zu ihren eigenen Gunsten aussagen würden. Auch der Beweiswert der Aussagen der als Zeugen angerufenen C.E._ und D.E._ wäre angesichts deren Nähe zu den Beschwerdeführern gering. Ebenso könne auf die persönliche Befragung der Beschwerdegegnerinnen verzichtet werden, da auch bei ihnen absehbar wäre, dass sie nicht zu ihren eigenen Ungunsten aussagen würden. Sodann vermöchten weder der offerierte Kostenvoranschlag oder eine gerichtliche Expertise noch ein Augenschein zu beweisen, welche Leistungen die Beschwerdeführer im Jahr 2004 erbracht hätten. Insbesondere könne auch aus der ins Recht gelegten Offerte des Malergeschäftes L._ vom 12. Januar 2009 nicht herausgelesen werden, welche Arbeiten die Beschwerdeführer zuvor selber durchgeführt haben sollten. Hingegen lasse gerade diese Offerte erhebliche Zweifel an der Qualität und damit am Wert der selbst ausgeführten Arbeiten aufkommen, wenn schon nach fünf Jahren seit den geltend gemachten Eigenleistungen derart umfassende Malerarbeiten, wie offeriert, als nötig erachtet würden.
Die Beschwerdeführer vermögen diese plausiblen Erwägungen nicht als willkürlich auszuweisen, indem sie lediglich auf ihrem Standpunkt beharren, die offerierten Beweise seien geeignet und könnten den erforderlichen Beweis erbringen.
Wie dargelegt (Erwägung 4.2) scheitert die geltend gemachte Verrechnungsforderung ohnehin bereits an der mangelnden Substantiierung. Die Vorinstanz hat daher die Verrechnungseinrede zu Recht verworfen. Weitere Einwendungen gegen die Zulässigkeit der Kündigung erheben die Beschwerdeführer nicht mehr. Die Vorinstanz hat somit die Kündigung wegen Zahlungsrückstandes ohne Bundesrechtsverletzung als gültig beurteilt.
5. Die Beschwerdeführer bleiben auch vor Bundesgericht bei ihrem Standpunkt, das Ausweisungsbegehren hätte mangels Aktivlegitimation der das Gesuch stellenden Erbengemeinschaft des G.H._, bestehend aus F.H._ und J.K.-H._, abgewiesen werden müssen. Gemäss Grundbuchauszug stehe die Liegenschaft X._ je zur Hälfte im Miteigentum von F.H._ und G.H._. Die Erbengemeinschaft des G.H._ sei demnach nur zur Hälfte am Mietobjekt berechtigt. Das nur die Erbengemeinschaft nennende Ausweisungsbegehren sei demnach nicht von der legitimen Vermieterschaft gestellt worden und hätte wegen Fehlens einer Partei der notwendigen Streitgenossenschaft abgewiesen werden müssen. Die Annahme einer irrigen Parteibezeichnung sei willkürlich.
Da die Erbengemeinschaft des G.H._ nicht alleinige Eigentümerin der Liegenschaft X._ ist, hätte das Ausweisungsgesuch an sich auch im Namen der Miteigentümerin F.H._ gestellt werden müssen. Dies hat die Vorinstanz zutreffend festgehalten. Es ist ihr aber auch darin zu folgen, dass bei der vorliegenden Konstellation dennoch nicht von einer fehlenden Aktivlegitimation ausgegangen werden musste, sondern von einer irrigen Bezeichnung der Parteien, die korrigiert werden durfte. Dies im Hinblick auf die bestehende Personalunion, die annehmen lässt, dass F.H._ sowohl in ihrer Eigenschaft als Miteigentümerin des hälftigen Anteils als auch als Mitglied der Erbengemeinschaft des G.H._, welcher der andere hälftige Mitgeigentumsanteil zusteht, auftrat, so dass jedenfalls alle Streitgenossen am Prozess beteiligt waren. Eine Bundesrechtsverletzung liegt nicht vor.
6. Die Beschwerde ist somit abzuweisen, soweit darauf eingetreten werden kann.
Aus den vorstehenden Erwägungen ergibt sich, dass die von den Beschwerdeführern im bundesgerichtlichen Verfahren gestellten Rechtsbegehren von Beginn an keinen Erfolg haben konnten. Dem Gesuch um unentgeltliche Rechtspflege kann deshalb nicht entsprochen werden (<ref-law>; vgl. <ref-ruling> E. 2.3.1).
Die Gerichtskosten sind damit von den unterliegenden Beschwerdeführern zu tragen (Art. 66 Abs. 1 und 5 BGG). Sie haben die anwaltlich vertretenen Beschwerdegegnerinnen überdies für das bundesgerichtliche Verfahren zu entschädigen (Art. 68 Abs. 2 und 4 BGG).

Demnach erkennt das Bundesgericht:
1. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
2. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
3. Die Gerichtskosten von Fr. 2'000.-- 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 insgesamt Fr. 2'500.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 13. Mai 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Widmer