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 Art. 272 OR 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. 