Sachverhalt:
A. A.a Die Ehegatten F._ und H._ reisten im Oktober 2000 erstmals in die Schweiz ein und stellten ein Asylgesuch. Nach dem rechtskräftigen Abschluss dieses ersten Asylverfahrens wurden sie im Dezember 2006 in ihr Heimatland Tunesien zurückgeschafft.
Im Juli 2007 kehrten die Ehegatten F._ und H._ in die Schweiz zurück und stellen ein neues Asylgesuch. Seit März 2008 erhielten sie von der Einwohnergemeinde X._ Sozialhilfe.
Mit Verfügung vom 8. September 2008 wies das Bundesamt für Migration (nachfolgend: BFM) das Asylgesuch der Ehegatten F._ und H._ ab und ordnete den Vollzug der Wegweisung an. Die dagegen erhobene Beschwerde wies das Bundesverwaltungsgericht mit Urteil vom 29. Oktober 2010 rechtskräftig ab. Gegen die Ablehnung des Asylgesuchs und die Wegweisung reichten die Ehegatten am 15. November 2010 beim UNO-Ausschluss gegen die Folter (Committee against Torture, CAT) Beschwerde ein. Das BFM setzte daher den Vollzug der Wegweisung aus der Schweiz vorläufig aus (Schreiben vom 29. November 2010).
A.b Mit Verfügung vom 11. Januar 2011 entschied die Einwohnergemeinde X._, dass den Ehegatten F._ und H._ keine Sozialhilfe, sondern lediglich noch Nothilfe ausgerichtet werde. Die tägliche finanzielle Unterstützung für Nahrung und Hygiene setzte sie mit Wirkung ab 1. Januar 2011 auf Fr. 14.- fest. Der Verbleib in der bisherigen Unterkunft wurde ihnen weiterhin gestattet. Überdies wurden sie gegen Krankheit versichert und konnten ärztliche Behandlung in Anspruch nehmen.
Gegen diese Verfügung erhoben die Ehegatten F._ und H._ Beschwerde beim Departement des Innern des Kantons Solothurn (nachfolgend: DDI). Dieses wies die Beschwerde am 10. März 2011 ab, soweit es darauf eintrat.
B. Gegen den Entscheid des DDI reichten die Ehegatten F._ und H._ beim Verwaltungsgericht des Kantons Solothurn Beschwerde ein, mit welcher sie die Aufhebung dieses Entscheids sowie der Verfügung der Einwohnergemeinde X._ beantragten und die Ausrichtung der Sozialhilfe bis zum Abschluss des Verfahrens vor dem UNO-Ausschuss gegen Folter verlangten. Das Verwaltungsgericht wies die Beschwerde mit Entscheid vom 11. Mai 2011 ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, eventuell subsidiärer Verfassungsbeschwerde lassen F._ und H._ die Aufhebung des Entscheids des Verwaltungsgerichts und die Ausrichtung von Sozialhilfe bis zum Abschluss des Verfahrens vor dem UNO-Ausschuss gegen die Folter beantragen. Zudem ersuchen sie um Gewährung der unentgeltlichen Rechtspflege (Befreiung von den Gerichtskosten).
Während das kantonale Gericht Abweisung der Beschwerde beantragt, soweit darauf eingetreten werden kann, verzichtet die Einwohnergemeinde X._ auf eine Vernehmlassung.
F._ und H._ reichen am 9. September 2011 eine weitere Stellungnahme ein.

Erwägungen:
1. Gegen den kantonal letztinstanzlichen Entscheid des Verwaltungsgerichts, der den Anspruch auf Sozialhilfe und damit eine öffentlich-rechtliche Angelegenheit betrifft, steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (Art. 82 lit. a, Art. 83, Art. 86 Abs. 1 lit. d und Art. 90 BGG). Die von den Beschwerdeführern eventualiter erhobene subsidiäre Verfassungsbeschwerde kommt daher nicht zum Zug (Art. 113 BGG).
2. 2.1 Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzung gemäss Art. 95 und Art. 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind. Es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (Urteil 8C_934/2008 vom 17. März 2009 E. 1 mit Hinweisen, nicht publ. in: <ref-ruling>, aber in: SVR 2009 UV Nr. 35 S. 120).
2.2 Nach Art. 105 BGG legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Abs. 1). Es kann diese Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Abs. 2). Die Voraussetzungen für eine Sachverhaltsrüge nach Art. 97 Abs. 1 BGG und für eine Berichtigung des Sachverhalts von Amtes wegen nach Art. 105 Abs. 2 BGG stimmen im Wesentlichen überein. Soweit es um die Frage geht, ob der Sachverhalt willkürlich oder unter verfassungswidriger Verletzung einer kantonalen Verfahrensregel ermittelt worden ist, sind strenge Anforderungen an die Begründungspflicht der Beschwerde gerechtfertigt. Entsprechende Beanstandungen sind vergleichbar mit den in Art. 106 Abs. 2 BGG genannten Rügen. Demzufolge genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Vielmehr ist in der Beschwerdeschrift nach den erwähnten gesetzlichen Erfordernissen darzulegen, inwiefern diese Feststellungen willkürlich bzw. unter Verletzung einer verfahrensrechtlichen Verfassungsvorschrift zustande gekommen sind. Andernfalls können Vorbringen mit Bezug auf einen Sachverhalt, der von den Feststellungen im angefochtenen Entscheid abweicht, nicht berücksichtigt werden. Vorbehalten bleiben offensichtliche Sachverhaltsmängel im Sinne von Art. 105 Abs. 2 BGG, die dem Richter geradezu in die Augen springen (<ref-ruling> E. 6.2 S. 288; <ref-ruling> E. 1.4.3 S. 245).
3. 3.1 Gemäss Art. 81 des Asylgesetzes vom 26. Juni 1998 (AsylG; SR 142.31) erhalten Personen, die sich gestützt auf das AsylG in der Schweiz aufhalten und die ihren Unterhalt nicht aus eigenen Mitteln bestreiten können, die notwendigen Sozialhilfeleistungen, sofern nicht Dritte aufgrund einer gesetzlichen oder vertraglichen Verpflichtung für sie aufkommen müssen, beziehungsweise auf Ersuchen hin Nothilfe. Für die Ausrichtung von Sozialhilfeleistungen und Nothilfe gilt kantonales Recht. Personen mit einem rechtskräftigen Wegweisungsentscheid, denen eine Ausreisefrist angesetzt worden ist, können von der Sozialhilfe ausgeschlossen werden (Art. 82 Abs. 1 AsylG und Art. 3 Abs. 3 der Asylverordnung 2 über Finanzierungsfragen vom 11. August 1999 [Asylverordnung 2, AsylV 2; SR 142.312]). Wird der Vollzug der Wegweisung für die Dauer eines ausserordentlichen Rechtsmittelverfahrens ausgesetzt, so erhalten abgewiesene Asylsuchende auf Ersuchen hin Nothilfe (Art. 82 Abs. 2 AsylG). Aus diesen Bestimmungen ergibt sich, dass eine Person mit rechtskräftigem Wegweisungsentscheid, der eine Ausreisefrist angesetzt worden ist, keinen Anspruch auf Sozialhilfe mehr hat, sondern nur noch auf die durch Art. 12 BV gewährleistete Nothilfe (<ref-ruling> E. 3.1 S. 115; <ref-ruling> E. 5.3 S. 123; je mit Hinweisen).
3.2 Entsprechend unterscheidet das Sozialgesetz des Kantons Solothurn vom 31. Januar 2007 (SG; BGS 831.1) drei Kategorien. Asyl- und schutzsuchende Personen ohne Aufenthaltsbewilligung erhalten Beiträge nach den Bestimmungen des Bundesrechts (§ 156 Abs. 1 SG), womit auf Art. 82 AsylG verwiesen wird. Eigentliche Sozialhilfe erhalten schutzsuchende Personen mit Aufenthaltsbewilligung und Flüchtlinge (§ 157 SG). Personen mit illegalem Aufenthalt, insbesondere auch Personen mit einem rechtskräftigen Nichteintretensentscheid, werden in Notlagen nur mit Nothilfe unterstützt (§ 158 Abs. 1 SG).
4. 4.1 Das kantonale Verwaltungsgericht ging davon aus, dass die Beschwerdeführer gestützt auf die obigen Bestimmungen keinen Anspruch auf Sozialhilfe mehr haben. Was diese beschwerdeweise dagegen vorbringen, ist nicht geeignet, daran etwas zu ändern.
4.2 Die Beschwerdeführer anerkennen ausdrücklich, dass sie mit dem Urteil des Bundesverwaltungsgerichts vom 29. Oktober 2010 rechtskräftig aus der Schweiz weggewiesen wurden. Sie rügen aber, zurzeit könne nicht von der "Ansetzung einer Ausreisefrist" gemäss Art. 82 Abs. 1 AsylG ausgegangen werden, da der Vollzug der Wegweisung am 29. November 2010 ausgesetzt worden sei.
Mit Verfügung vom 4. November 2010 teilte das BFM den Beschwerdeführern mit, mit dem Urteil des Bundesverwaltungsgerichts sei die Ablehnung des Asylgesuchs bzw. die Wegweisung aus der Schweiz in Rechtskraft erwachsen. Daher werde ihnen eine Ausreisefrist bis 2. Dezember 2010 angesetzt. Es geht somit nicht darum, dass keine Ausreisefrist angesetzt wurde, sondern dass der Vollzug der (mit Frist angeordneten) Wegweisung ausgesetzt wurde (Art. 82 Abs. 2 AsylG).
4.3 Nach Auffassung der Beschwerdeführer ist Art. 82 Abs. 2 AsylG nicht anwendbar, da diese Bestimmung nur die Dauer eines ausserordentlichen Rechtsmittelverfahrens betreffe. Als ausserordentliche Rechtsmittel gälten insbesondere die Aufsichtsbeschwerde und das Wiedererwägungsgesuch, welche die angerufene Instanz nicht zur Behandlung verpflichten. Die beim UNO-Ausschuss gegen Folter eingereichte Beschwerde sei kein ausserordentliches Rechtsmittel in diesem Sinn, da sie an formelle Voraussetzungen gebunden sei.
Damit verkennen die Beschwerdeführer den Begriff des ausserordentlichen Rechtsmittels. Ein solches richtet sich gegen formell rechtskräftige Verfügungen und Entscheide. Demgegenüber ermöglichen ordentliche Rechtsmittel den Weiterzug einer Streitsache innerhalb des funktionellen Instanzenzugs und hemmen den Eintritt der formellen Rechtskraft des angefochtenen Entscheids (ALFRED KÖLZ/JÜRG BOSSHART/MARTIN RÖHL, Kommentar zum Verwaltungsrechtspflegegesetz des Kantons Zürich, 2. Aufl. 1999, N. 7 der Vorbemerkungen zu §§ 19-28; URSINA BEERLI-BONORAND, Die ausserordentlichen Rechtsmittel in der Verwaltungsrechtspflege des Bundes und der Kantone, 1985, S. 30). Genau in diesem Sinn wird der Begriff denn auch in Art. 82 Abs. 2 AsylG verstanden, wie auch der systematische Zusammenhang mit Abs. 1 und die ratio legis dieser Norm verdeutlichen. Es geht darum, dass zwar ein rechtskräftiger Wegweisungsentscheid vorliegt, dessen Vollzug aber ausgesetzt ist. Der Entscheid des UNO-Ausschusses gegen Folter (vgl. Übereinkommen gegen Folter und andere grausame, unmenschliche oder erniedrigende Behandlung oder Strafe (SR 0.105) ist rechtlich nicht bindend. Der Beschwerde an den Ausschuss kommt keine aufschiebende Wirkung zu (WALTER KÄLIN/JÖRG KÜNZLI, Universeller Menschenrechtsschutz, 2. Aufl. 2008, S. 250 f.; MARIO GATTIKER, Die Beschwerde gemäss Art. 22 UNO-Folterkonvention, in: Asyl 1/1996, S. 3 ff., S. 3 und S. 6). Diese ändert somit nichts an der Rechtskraft des Wegweisungsentscheids. Ob die Vollstreckung des Wegweisungsentscheids ausgesetzt wird aufgrund eines Ermessensentscheids der Vollzugsbehörde oder weil der UNO-Ausschuss gegen Folter mittels vorsorglicher Massnahmen die vorläufige Nicht-Vollstreckung angeordnet hat (vgl. dazu und zu der nach der Praxis der UNO-Organe verbindlichen Wirkung einer vorsorglichen Massnahme für den betroffenen Staat: KÄLIN/KÜNZLI, a.a.O., S. 252 f. und bei Anm. 48), ist gemäss Art. 82 Abs. 2 AsylG nicht entscheidend. Auf jeden Fall haben die Beschwerdeführer nur Anspruch auf Nothilfe.
5. 5.1 Eventualiter rügen die Beschwerdeführer eine Verletzung von Art. 12 BV durch die im Rahmen der Nothilfe gewährte Unterkunft. Der Ehegatte leide an einer mittelgradigen bis schweren Episode einer rezidivierenden depressiven Störung. Gemäss Einschätzung des behandelnden Arztes in dessen Bericht vom 19. Januar 2011 leide er unter der aktuellen Wohnsituation im Asylzentrum, die von einem hohen Lärmpegel und einer generellen Hektik geprägt sei. Er bedürfe vermehrter Ruhe und Privatsphäre.
5.2 Die Beschwerdeführer begründen somit die geltend gemachte Verletzung von Art. 12 BV einzig mit der Wohnsituation. Angesichts des Rügeprinzips (vgl. E. 2.1) ist somit auch nur dieser Punkt zu prüfen. Auf die noch vor Vorinstanz gerügten Umstände ist nicht weiter einzugehen. Die Vorinstanz hielt bezüglich der Wohnsituation fest, aufgrund der Akten sei davon auszugehen, dass den Beschwerdeführern infolge des bereits im vorinstanzlichen Verfahren eingereichten Arztberichts vom 19. Januar 2011 eine neue Wohnung zugeteilt worden sei. Die Beschwerdeführer gehen nicht auf diese Sachverhaltsfeststellung ein und rügen sie insbesondere nicht als willkürlich (vgl. E. 2.2). Ihre Beschwerdebegründung ist angesichts der vorinstanzlichen Feststellungen nicht nachvollziehbar.
6. Die Beschwerde ist somit abzuweisen. Die Gerichtskosten werden den unterliegenden Beschwerdeführern auferlegt (Art. 66 Abs. 1 BGG). Dem Gesuch um unentgeltliche Rechtspflege (im Sinne der vorläufigen Befreiung von den Gerichtskosten) kann entsprochen werden, da die Bedürftigkeit ausgewiesen ist und die Beschwerde nicht als aussichtslos zu bezeichnen ist (Art. 64 Abs. 1 BGG). Es wird indessen ausdrücklich auf Art. 64 Abs. 4 BGG aufmerksam gemacht, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten haben wird, wenn sie später dazu im Stande ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Den Beschwerdeführern wird die unentgeltliche Rechtspflege gewährt.
3. Die Gerichtskosten von Fr. 500.- werden den Beschwerdeführern auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Solothurn schriftlich mitgeteilt.
Luzern, 5. Oktober 2011
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Ursprung
Die Gerichtsschreiberin: Hofer