Sachverhalt:
A. Die 1962 geborene, iranische Staatsangehörige S._ reiste 1993 mit ihrer Mutter und drei Geschwistern in die Schweiz ein und stellte ein Asylgesuch, welches 1996 abgewiesen wurde. Die mit der Wegweisung verbundene Ausreisefrist lief am 15. November 1996 ab. Während ihre Mutter und zwei Geschwister in die USA ausgeschafft wurden, duldete das kantonale Migrationsamt S._ und ihre Schwester Z._ in der Schweiz. Das Amt für soziale Sicherheit des Kantons Solothurn verfügte am 13. Dezember 2007 den Ausschluss aus dem System der Sozialhilfe mit Wegweisung aus der Asylstruktur, sodass ihnen ab 1. Januar 2008, sofern beantragt, einzig Nothilfe gewährt würde. Das Amt führte weiter aus, damit ende der bestehende Krankenversicherungsschutz und sie habe die Wohnung bis 31. März 2008 zu verlassen. Auf Wunsch könne sie in die kantonale Kollektivunterkunft X._ ziehen. S._ verblieb in der Wohnung an der Strasse Y._ in B._, die sie sich mit ihrer Schwester und deren Freund teilt, und bezog keine Nothilfe; das Amt für soziale Sicherheit übernahm einzig weiterhin die administrative und finanzielle Regelung der Krankenversicherung. Am 31. Mai 2011 teilte es S._ mit, da sie seit drei Jahren keine Anträge auf Nothilfeleistungen gestellt habe, sei von einer wirtschaftlichen Selbstständigkeit auszugehen, weshalb sie ab 31. Juli 2011 nicht mehr unterstützt und die kollektive Krankenversicherung in eine Einzelversicherung umgewandelt werde. Für die Versicherungsprämien und allfällige weitere Krankenkassenansprüche habe sie selbst aufzukommen. Nachdem S._ am 18. Juni 2011 Nothilfe und Weiterführung der bisherigen Krankenversicherung geltend machte, hielt das Amt in einem Schreiben vom 7. Juli 2011 fest, die Nothilfe werde nur integral ausgerichtet, was bedeute, dass finanzielle Nothilfe nicht ausserhalb einer kantonalen Unterbringungsstruktur gewährt werde. Dementsprechend verfügte das Departement des Innern am 25. Juli 2011, dass die Anträge auf Nothilfe in B._ und Beibehaltung der bisherigen Krankenversicherung abgewiesen werde. Sofern die Voraussetzungen gegeben seien, werde im Zentrum X._ Nothilfe gewährt. Per 1. August 2011 werde sie aus der kollektiven Krankenversicherung ausscheiden und zum Übertritt in die Einzelversicherung angemeldet.
B. Die hiegegen geführte Beschwerde wies das Verwaltungsgericht des Kantons Solothurn mit Entscheid vom 16. Dezember 2011 ab.
C. S._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und beantragen, in Aufhebung des vorinstanzlichen Entscheids sei ihr Nothilfe in B._ zu gewähren. Das Departement des Innern des Kantons Solothurn sei zu verpflichten, ab 1. August 2011 weiterhin für die Kosten der bisherigen obligatorischen Krankenversicherung aufzukommen. Es wird um aufschiebende Wirkung der Beschwerde ersucht, weshalb das Departement des Innern des Kantons Solothurn für die Dauer des Verfahrens die Kosten für die kollektive Krankenversicherung zu übernehmen habe. Ferner sei ihr die unentgeltliche Rechtspflege zu gewähren.
Das Amt für soziale Sicherheit schliesst auf Abweisung der Beschwerde und das Verwaltungsgericht beantragt ebenfalls deren Abweisung, soweit darauf einzutreten sei.
D. Mit Eingabe vom 15. Februar 2012 lässt S._ ein Schreiben des Amtes für soziale Sicherheit vom 13. Februar 2012 zukommen, wonach dieses bis zum Abschluss des hängigen Beschwerdeverfahrens auf eine Änderung der bisherigen Ausgestaltung der Krankenversicherung verzichtet. Die Beschwerdeführerin bekräftigt zudem ihren Standpunkt mit Eingabe vom 27. Februar 2012.
Erwägungen:
1. 1.1 Gestützt auf Art. 82 lit. a BGG beurteilt das Bundesgericht Beschwerden gegen Entscheide in Angelegenheiten des öffentlichen Rechts. Dieses Rechtsmittel steht somit grundsätzlich auch auf dem Gebiet der kantonalen Sozialhilfe zur Verfügung. Das Bundesgerichtsgesetz enthält dazu in Art. 83 keinen Ausschlussgrund.
1.2 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Der vorinstanzliche Entscheid stützt sich in der Sache auf kantonales Recht. Als Beschwerdegrund kommt zur Hauptsache die Verletzung von Bundesrecht, insbesondere von verfassungsmässigen Rechten der Bundesverfassung in Frage (Art. 95 BGG). Die Anwendung des kantonalen Rechts als solches bildet nicht Beschwerdegrund. Überprüft werden kann insoweit nur, ob der angefochtene Entscheid auf willkürlicher Gesetzesanwendung beruht oder ob das Gesetz oder seine Anwendung sonst wie gegen übergeordnetes Recht verstossen (vgl. BGE 133 II 249 E. 1.2.1 S. 251 f.). Hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht gilt eine qualifizierte Rügepflicht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG; BGE 136 I 49 E. 1.4.1 S. 53). Wird eine Verletzung des Willkürverbots geltend gemacht, muss im Einzelnen dargelegt werden, inwiefern der angefochtene Entscheid an einem qualifizierten und offensichtlichen Mangel leidet. Auf ungenügend begründete Rügen und bloss allgemein gehaltene, appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein (BGE 8C_294/2011 vom 29. Dezember 2011 E. 2.1; 130 I 258 E. 1.3 S. 262; 129 I 113 E. 2.1 S. 120; je mit Hinweisen).
1.3 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, genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Vielmehr ist in der Beschwerdeschrift 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 geradezu in die Augen springen (BGE 8C_294/2011 vom 29. Dezember 2011 E. 2.2 mit Hinweisen).
2. 2.1 Nach Art. 12 BV hat, wer in Not gerät und nicht in der Lage ist, für sich zu sorgen, Anspruch auf Hilfe und Betreuung und auf die Mittel, die für ein menschenwürdiges Dasein unerlässlich sind. Dieses Grundrecht garantiert nicht ein Mindesteinkommen; verfassungsrechtlich geboten ist nur, was für ein menschenwürdiges Dasein unabdingbar ist und vor einer unwürdigen Bettelexistenz zu bewahren vermag. Der Anspruch umfasst einzig die in einer Notlage im Sinne einer Überbrückungshilfe unerlässlichen Mittel (in Form von Nahrung, Kleidung, Obdach und medizinischer Grundversorgung), um überleben zu können. Diese Beschränkung des verfassungsrechtlichen Anspruches auf ein Minimum im Sinne einer "Überlebenshilfe" bedeutet, dass Schutzbereich und Kerngehalt zusammenfallen. Durch das ausdrückliche Erwähnen des Subsidiaritätsprinzips hat der Verfassungsgeber somit (bereits) den Anspruch als solchen relativiert. Grundsätzliche Voraussetzung der Anwendbarkeit von Art. 12 BV ist das Vorliegen einer aktuellen, d.h. tatsächlich eingetretenen oder unmittelbar drohenden Notlage (BGE 131 I 166 E. 3.1 S. 172, E. 3.2 S. 173, 130 I 71 E. 4.1 S. 74 f., je mit Hinweisen). Art 12 BV umfasst nur eine auf die konkreten Umstände zugeschnittene, minimale individuelle Nothilfe. Sie beschränkt sich auf das absolut Notwendige und soll die vorhandene Notlage beheben. Insofern unterscheidet sich der verfassungsmässige Anspruch auf Hilfe in Notlagen vom kantonalen Anspruch auf Sozialhilfe, die umfassender ist (MARGRITH BIGLER-EGGENBERGER, in: Die Schweizerische Bundesverfassung, Ehrenzeller und andere [Hrsg.], 2. Aufl. 2008, N. 12, 13 und 20 zu Art. 12 BV).
2.2 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 (BGE 137 I 113 E. 3.1 S. 115; 135 I 119 E. 5.3 S. 123; je mit Hinweisen).
2.3 Nach dem Sozialgesetz des Kantons Solothurn vom 31. Januar 2007 (SG/SO; BGS 831.1) werden Personen mit illegalem Aufenthalt, insbesondere auch Personen mit einem rechtskräftigen Nichteintretensentscheid, in Notlagen mit Nothilfe unterstützt (§ 158 Abs. 1 SG/SO). Gemäss § 93 Abs. 3 der Sozialverordnung vom 29. Oktober 2007 (SV/SO; BGS 831.2) erhalten Personen, die mit rechtskräftigem Nichteintretens- oder Abweisungsentscheid weggewiesen werden, keine Leistungen nach den SKOS-Richtlinien. Sie sind nur im Rahmen der Nothilfe zu unterstützen. Vorbehalten bleiben Härtefälle. Der Regierungsrat erlässt Richtlinien.
Der Regierungsratsbeschluss Nr. 2007/2002 vom 27. November 2007 hält dementsprechend fest, dass die Nothilfe nach Möglichkeit in Sachleistungen erbracht wird. Wenn es zweckmässig erscheint, können auch Geldleistungen ausbezahlt werden. Das Amt für soziale Sicherheit, Sozialhilfe und Asyl (ASO SOA) befindet über die Form der Ausrichtung (Ziff. 3.5). Personen mit rechtskräftigem Nichteintretensentscheid oder Abweisungsentscheid und Wegweisungsentscheid werden grundsätzlich aus den Gemeindestrukturen weggewiesen (Ziff. 3.6). Weggewiesene Personen, welche darlegen, in einer Notlage zu sein, sind an die Anlaufstelle des ASO SOA zu verweisen. Das ASO SOA weist diesen Personen bei Vorliegen einer Notlage einen Unterkunftsplatz bzw. Aufenthaltsort zu (Ziff. 3.7). In Härtefällen können Personen mit einem erhöhten Schutzbedürfnis weiterhin in den Gemeindestrukturen verweilen. Es kommen aber für Nahrung und Hygiene die nachgenannten Ansätze zur Anwendung. Das ASO SOA bezeichnet die berechtigten Personen und instruiert die örtlichen Sozialhilfeorgane (Ziff. 3.8). Nothilfe umfasst Gewährleistung von Obdach, Essen, Kleidung, Hygiene und medizinischer Notversorgung. Über eine eventuelle Weiterführung des Krankenversicherungsschutzes entscheidet das ASO SOA auf Antrag (Ziff. 3.9).
3. Streitig ist der Anspruch auf Nothilfe am Aufenthaltsort der Beschwerdeführerin in B._ in Form der Übernahme der Prämien der obligatorischen Krankenversicherung durch das Amt für soziale Sicherheit.
3.1 Das kantonale Verwaltungsgericht gelangte zum Schluss, gestützt auf den vom Regierungsrat erlassenen Beschluss (Nr. 2007/2002 vom 27. November 2007) sei es zulässig, dass die Beschwerdeführerin aus den Gemeindestrukturen weggewiesen worden sei und dass der Kanton den Aufenthaltsort bestimme. Dementsprechend könne das Amt für soziale Sicherheit die Leistungen der Nothilfe, namentlich die Kostenübernahme der (kollektiven) Krankenversicherung, an die Bedingung knüpfen, dass sich die Beschwerdeführerin an einem ihr zugewiesenen Unterkunftsplatz aufhalte. Dieses Vorgehen verstosse nicht gegen Art. 12 BV. Gründe, die im Sinne eines Härtefalls den Verbleib in B._ rechtfertigen würden, seien nicht ersichtlich.
3.2 Soweit die solothurnischen Behörden die tatsächliche Notlage der Beschwerdeführerin in Frage stellen, wozu die Vorinstanz keine Feststellungen getroffen hat, kann ihnen nicht gefolgt werden, zumal sie ihre Entscheide auch nicht mit dem Fehlen dieser Voraussetzung begründeten. Mit Blick auf die Notlage der Beschwerdeführerin steht fest, dass sie nach Einstellung der Sozialhilfeleistungen per 1. Januar 2008 - auch wenn sie erst auf die am 31. Mai 2011 ergangene Mitteilung hin, ab 1. August 2011 werde ihr Unterstützungsfall abgeschlossen, um die weitere behördliche Übernahme der Krankenkassenprämien ersuchte - im Umfang dieser Prämien nie ohne staatliche Hilfeleistungen auskam. Als weggewiesene Ausländerin kann die Beschwerdeführerin ohne geregelten Aufenthaltsstatus grundsätzlich keine Bewilligung zur Erwerbstätigkeit erhalten (vgl. Art. 43 Abs. 2 und Art. 14 AsylG), auch wenn die Leiterin für Ausländerfragen in einem Schreiben vom 31. Mai 2007 anführte, einen Stellenantritt ausnahmsweise wohlwollend zu prüfen. Es ist davon auszugehen, dass sich die Beschwerdeführerin in einer Notlage befindet, aus der sie sich auch mit zumutbaren Anstrengungen nicht selbst befreien kann (BGE 135 I 119 E. 7.2 S. 126).
4. 4.1 Der seit 1. August 2011 in Kraft stehende Art. 92d KVV (SR 832.102) regelt die Prämienübernahme von nothilfeberechtigten Personen, indem gemäss Abs. 1 dieser Bestimmung auf nothilfeberechtigte Personen nach Art. 82 AsylG die Artikel 82a AsylG und 105a KVG sinngemäss anwendbar sind.
4.2 Wie das Bundesamt für Gesundheit (BAG) in einer Medienmitteilung vom 6. Juli 2011 festhielt, sind damit Nothilfeberechtigte obligatorisch krankenversichert, sofern sie in der Schweiz Wohnsitz haben. Die Versicherungspflicht endet mit der Ausreise aus der Schweiz. Abgewiesene Asylsuchende und Asylsuchende mit einem rechtskräftigen Nichteintretensentscheid, die die Schweiz nicht verlassen, bleiben somit bis zur Ausreise aus der Schweiz der obligatorischen Krankenversicherung unterstellt.
4.3 Die Beschwerdeführerin rügt eine Verletzung dieser bundesrechtlichen Bestimmung. Die vorinstanzliche Argumentation, mit der Umschreibung von der Kollektiv- in eine Einzelversicherung sei ihr der Zugang zur obligatorischen Krankenversicherung nicht verwehrt, sei willkürlich und unhaltbar.
4.4 Streitig ist die Übernahme der Krankenkassenprämien durch den Staat ab Inkrafttreten dieser Bestimmung. Gemäss der Übergangsbestimmung zur Änderung vom 6. Juli 2011 sind die Prämien und der Aufschlag nach dieser Änderung rückwirkend ab dem Inkrafttreten dieser Änderung geschuldet, wenn ein Versicherer ein Gesuch um Kostenübernahme von einer nothilfeberechtigten Person erhält, deren Asylentscheid vor dem Inkrafttreten dieser Änderung rechtskräftig entschieden wurde. Damit ist diese Rechtsnorm auf den vorliegenden Sachverhalt anwendbar. Als nothilfeberechtigte, abgewiesene Asylsuchende ist die Beschwerdeführerin ab 1. August 2011 gestützt auf Art. 92d KVV obligatorisch krankenversichert und die Prämien sind durch das Amt für Soziale Sicherheit zu übernehmen.
5. 5.1 Es bleibt zu prüfen, ob vorliegend die Prämienübernahme der obligatorischen Krankenversicherung mit der Auflage des Umzugs der Beschwerdeführerin in eine kantonal vorgesehene Unterbringungsstruktur verknüpft werden kann.
5.2 Art. 92d KVV sieht keine Möglichkeit vor, den obligatorischen Krankenversicherungsschutz von nothilfeberechtigten Personen nach Art. 82 AsylG mit Nebenbestimmungen wie Auflagen oder Bedingungen zu versehen. Indem Abs. 1 dieser Verordnungsbestimmung Art. 82a AsylG als sinngemäss anwendbar erklärt, sind einzig Einschränkungen hinsichtlich Wahl des Versicherers und der Leistungserbringer im Sinne von Art. 82a AsylG vorgesehen. Zwar bedürfen Nebenbestimmungen wie Auflagen oder Bedingungen nicht zwingend einer im Gesetz ausdrücklich wiedergegebenen Grundlage; ihre Zulässigkeit kann sich unter Umständen auch unmittelbar aus dem Gesetzeszweck und dem damit zusammenhängenden öffentlichen Interesse ergeben. Sachfremde Nebenbestimmungen sind aber unzulässig. Ferner müssen Nebenbestimmungen auch mit dem Grundsatz der Verhältnismässigkeit vereinbar sein, was bedeutet, dass sie u.a. für die Erreichung des angestrebten Ziels erforderlich sein müssen (HÄFELIN/MÜLLER/UHLMANN, Allgemeines Verwaltungsrecht, 6. Aufl. 2010, Rz. 918 ff.). Mit den Nebenbestimmungen werden die rechtmässige Ausübung eines eingeräumten Rechts oder einer Bewilligung oder die zweckkonforme Verwendung von staatlichen Leistungen sichergestellt (BGE 131 I 166 E. 4).
5.3 Die Beschwerdeführerin ersucht nicht um Obdach, sondern einzig um finanzielle Unterstützung in Form von Fortführung der bisherigen Krankenkassenprämienleistung durch das Amt für soziale Sicherheit. Insofern diktiert sie damit - entgegen der Ansicht der Beschwerdegegnerin - nicht die Art der Nothilfeleistung in Bezug auf die Unterbringung, da sie in diesem Punkt nicht nothilfebedürftig ist. In Berücksichtigung des auch im Rahmen der Nothilfe geltenden Grundsatzes der Subsidiarität (vgl. etwa BGE 131 I 166 E. 4.1 S. 173 mit Hinweisen sowie CHRISTOPH HÄFELI, Prinzipien der Sozialhilfe, in: Das Schweizerische Sozialhilferecht, 2008, S. 73 ff.) gehen tatsächlich erbrachte Leistungen Dritter, die einen Teil der elementaren Grundbedürfnisse abdecken und auf die kein durchsetzbarer Rechtsanspruch besteht, dem Leistungsanspruch gegenüber dem Staat vor. Zumindest soweit und solange die Beschwerdeführerin in der Wohnung an der Strasse Y._ in B._ verbleiben kann und der Lebenspartner ihrer Schwester die Mietzinse derselben trägt, ist die Beschwerdeführerin hinsichtlich Unterkunft nicht nothilfebedürftig. Wie dargelegt (E. 4), hat die Beschwerdeführerin nicht nur den grundrechtlich geschützten Anspruch auf medizinische Notfallversorgung, sondern sie ist - darüber hinaus - als Nothilfeberechtigte ab 1. August 2011 kraft Bundesrecht obligatorisch krankenversichert. Wenn das Amt seine weitere Übernahme der dementsprechend anfallenden Krankenkassenprämien mit der Auflage verknüpfen will, dass die Beschwerdeführerin die vom Freund ihrer Schwester finanzierte Wohnung zu verlassen und in die kantonale Kollektivunterkunft zu ziehen hat, ist dies sachfremd und dient nicht der Sicherstellung einer zweckkonformen Verwendung der staatlichen Leistungen. Dürfte sich die Beschwerdeführerin nicht mehr in der vor Jahren bezogenen Wohnung aufhalten, um die ersuchte finanzielle Leistung zu erhalten, würde dies vielmehr zusätzlich die Notlage hinsichtlich der Unterkunft aktualisieren, die finanzielle Unmöglichkeit der Beschwerdeführerin, die Krankenversicherungskosten selbst zu tragen, hingegen nicht beseitigen.
Überdies ist auch das vorinstanzliche Argument, die Zuweisung einer Unterkunft gewähre die Kontrolle der zugesprochenen Nothilfe, nicht stichhaltig, da die administrative Abwicklung der Krankenversicherungskosten hier so oder anders direkt durch das Amt für Soziale Sicherheit erfolgt, was dem Amt eine genügende Kontrolle der aus der obligatorischen Krankenversicherung anfallenden Kosten erlaubt. Daran würde auch ein Umzug nichts ändern. Die Durchsetzung der behördlichen Auflage einer Unterbringung in der Kollektivunterkunft beseitigt weder die bestehende Notlage noch dient sie einer zweckkonformen Umsetzung des Versicherungsschutzes nach Art. 92d KVV, weshalb die Nebenbestimmung unzulässig ist.
6. Bei diesem Ergebnis ist auf die Rügen, die vorinstanzlich bestätigte Vorschreibung des Aufenthaltsorts verletze den verfassungsmässigen Anspruch auf Nothilfe nach Art. 12 BV, sowie das in Art. 8 EMRK und Art. 13 BV umschriebene Recht auf Bewegungsfreiheit und das Diskriminierungsverbot von Art. 2 Abs. 2 UNO-Pakt I sowie Art. 8 Abs. 2 BV, nicht näher einzugehen.
7. Nachdem das Amt für soziale Sicherheit mit Schreiben vom 13. Februar 2012 auf eine Änderung der bisherigen Ausgestaltung der Krankenversicherung bis zum Abschluss dieses Verfahrens verzichtet hat, wird, wie der Rechtsvertreter in seiner Eingabe vom 15. Februar 2012 bereits festhielt, das Gesuch um aufschiebende Wirkung der Beschwerde hinfällig.
8. Die Gerichtskosten sind vom Beschwerdegegner als unterliegender Partei zu tragen (Art. 66 Abs. 1 BGG). Der Beschwerdeführerin steht bei diesem Verfahrensausgang überdies eine Parteientschädigung zu (Art. 68 Abs. 2 BGG), womit deren Gesuch um unentgeltliche Rechtspflege gegenstandslos wird.
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der Entscheid des Verwaltungsgerichts des Kantons Solothurn vom 16. Dezember 2011 und die Verfügung des Departements des Innern des Kantons Solothurn vom 25. Juli 2011 werden aufgehoben.
2. Das Gesuch um aufschiebende Wirkung wird als gegenstandslos abgeschrieben.
3. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdegegner auferlegt.
4. Der Beschwerdegegner hat die Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
5. Die Sache wird zur Neuverlegung der Parteientschädigung des vorangegangenen Verfahrens an das Verwaltungsgericht des Kantons Solothurn zurückgewiesen.
6. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Solothurn schriftlich mitgeteilt.
Luzern, 21. August 2012
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Ursprung
Die Gerichtsschreiberin: Polla