Sachverhalt:
A. Die 1915 geborene, verheiratete S._ hatte ihren Wohnsitz in X._, Kanton Wallis. Im Juli 2010 trat sie in das Alterszentrum Y._, Kanton St. Gallen, ein und meldete sich am 6. Dezember 2010 beim Einwohneramt an; das Einwohneramt vermerkte den Zuzug per 21. Oktober 2010. Nachdem S._ um Pflegefinanzierung ersucht hatte (Anmeldung vom 31. Dezember 2010; eingegangen bei der Sozialversicherungsanstalt des Kantons St. Gallen am 3. Februar 2011), ergab sich zwischen der Sozialversicherungsanstalt des Kantons St. Gallen und der Ausgleichskasse des Kantons Wallis eine Kontroverse betreffend Zuständigkeit für die Kostenübernahme. Mit Verfügung vom 5. Juli 2011 verneinte die Sozialversicherungsanstalt des Kantons St. Gallen ihre Zuständigkeit und trat auf das Gesuch um Pflegefinanzierung nicht ein.
B. Hiegegen erhob S._ Beschwerde mit dem Antrag, unter Aufhebung der Verfügung sei die Sozialversicherungsanstalt anzuweisen, auf das Gesuch um Pflegefinanzierung einzutreten. Auch das Gesundheitsdepartement des Kantons Wallis führte Beschwerde mit demselben Rechtsbegehren. Das Versicherungsgericht des Kantons St. Gallen vereinigte die Verfahren, trat auf die Beschwerden mit Entscheid vom 19. Januar 2012 nicht ein und entschied, diese seien zuständigkeitshalber dem kantonalen Departement des Innern zu überweisen.
C. Die Sozialversicherungsanstalt des Kantons St. Gallen führt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt die Aufhebung des angefochtenen Entscheids sowie die Rückweisung der Sache an die Vorinstanz zur (materiellen) Entscheidung.
Das Versicherungsgericht und der Kanton Wallis verzichten auf eine Vernehmlassung, S._ und das Departement des Innern des Kantons St. Gallen schliessen auf Gutheissung der Beschwerde.

Erwägungen:
1. 1.1 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist unter anderem zulässig gegen Entscheide, die das Verfahren abschliessen (<ref-law>). Der vorinstanzliche Nichteintretensentscheid kann als Endentscheid im Sinne von <ref-law> (Urteil 9C_740/2008 vom 10. Oktober 2008 E. 1) oder als - selbstständig eröffneter - Vor- oder Zwischenentscheid über die Zuständigkeit nach <ref-law> betrachtet werden. Die dagegen erhobene Beschwerde in öffentlich-rechtlichen Angelegenheiten ist somit zulässig (<ref-ruling> E. 1 S. 126).
1.2 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann die Verletzung von Bundesrecht gerügt werden (<ref-law>). Soweit sich der angefochtene Entscheid auf Quellen des kantonalen Rechts stützt, welche nicht in Art. 95 lit. c-e BGG genannt werden, beschränkt sich die Überprüfung durch das Bundesgericht inhaltlich auf die Frage, ob die Anwendung des kantonalen Rechts zu einer Bundesrechtswidrigkeit führt. Im Vordergrund steht dabei eine Verletzung verfassungsmässiger Rechte (<ref-ruling> E. 1 S. 203 mit Hinweisen).
2. 2.1 Die Restfinanzierung im Bereich der Pflegekosten betrifft eine Leistung, die nicht von der obligatorischen Krankenversicherung getragen wird. Es fragt sich daher, ob die Zuständigkeit zur Behandlung der Beschwerde bei der II. sozialrechtlichen Abteilung des Bundesgerichts liegt (Art. 35 lit. d des Reglements vom 20. November 2006 für das Bundesgericht [BgerR; SR 173.110.131]) oder bei der II. öffentlich-rechtlichen Abteilung (Art. 30 Abs. 1 lit. c Ziff. 14 BgerR).
2.2 Für die Zuteilung eines Geschäfts an eine Abteilung ist die Rechtsfrage massgeblich, auf der das Schwergewicht der Entscheidung liegt, wobei von der reglementarischen Geschäftsverteilung im Einzelfall aufgrund der Natur des Geschäfts und seiner Konnexität mit anderen Geschäften abgewichen werden kann. Vorausgesetzt wird eine Einigung der Präsidenten und Präsidentinnen der betroffenen Abteilungen (Art. 36 Abs. 1 und 2 BgerR). Im Rahmen des Verfahrens 2C_796/2011 (Urteil vom 10. Juli 2012) erfolgte ein Meinungsaustausch zwischen der II. öffentlich-rechtlichen und der II. sozialrechtlichen Abteilung des Bundesgerichts, welcher ergab, dass Streitigkeiten nach Eintritt eines Leistungsfalles in die Zuständigkeit der II. sozialrechtlichen Abteilung fallen, wenn - allenfalls auch nur im Hintergrund - sozialversicherungsrechtliche Leistungen umstritten sind, wozu auch die kantonale Restfinanzierung der Pflegekosten gehört. Die übrigen - abstrakten - spital- und pflege(finanzierungs)rechtlichen Streitigkeiten sind als Angelegenheiten des öffentlichen Gesundheitsrechts von der II. öffentlich-rechtlichen Abteilung zu beurteilen. Damit ist die Zuständigkeit der II. sozialrechtlichen Abteilung für die Behandlung der vorliegenden Beschwerde gegeben und es ist auf diese einzutreten.
3. Streitig ist die innerkantonale Zuständigkeit zur Beurteilung der Rechtmässigkeit des Nichteintretensentscheides der Sozialversicherungsanstalt. In diesem Zusammenhang stellt sich insbesondere die Rechtsfrage, ob auf Streitigkeiten betreffend die Pflegefinanzierung (<ref-law>) die (verfahrensrechtlichen) Bestimmungen des Bundesgesetzes vom 6. Oktober 2000 über den Allgemeinen Teil des Sozialversicherungsrechts (ATSG; SR 830.1) zur Anwendung gelangen. Trifft dies zu, richtet sich der Rechtsweg nach <ref-law> und es ist das kantonale Versicherungsgericht zuständig.
4. 4.1 Die Vorinstanz erwog, <ref-law> sei mit <ref-law> (Kostenübernahme bei Hospitalisation in einem nicht auf der Spitalliste des Wohnkantons aufgeführten Spital) vergleichbar. Nach der Rechtsprechung zu <ref-law> ergebe sich die Zuständigkeit des Versicherungsgerichtes trotz fehlendem Vorbehalt in <ref-law> nicht aus dem ATSG, sondern es sei das kantonale Recht massgebend. Obwohl die Differenzzahlungspflicht gemäss <ref-law> sozialversicherungsrechtlicher Natur sei, gälten die Kantone nicht als Versicherer im Sinne des KVG, weshalb nicht das kantonale Versicherungsgericht gestützt auf das ATSG zuständig sei. Nichts anderes könne für die Pflegefinanzierung gemäss <ref-law> gelten, welche ebenfalls Subventionscharakter habe und nicht das Verhältnis zwischen Versicherten und Krankenversicherung beschlage. Zudem falle die Regelung von Zuständigkeit und Verfahren im Bereich der Restfinanzierung grundsätzlich - als selbstständiges kantonales Recht - in die Kompetenz der Kantone. Auch aus diesem Grund könne das ATSG keine Anwendung finden. Zuständig sei vielmehr nach Art. 43bis Abs. 1 lit. a des Gesetzes des Kantons St. Gallen vom 16. Mai 1965 über die Verwaltungsrechtspflege (sGS 951.1) in Verbindung mit Art. 22 Abs. 1 lit. i Geschäftsreglement der Regierung und der Staatskanzlei vom 7. Dezember 1951 (sGS 141.3) das kantonale Departement des Innern.
4.2 Die beschwerdeführende Sozialversicherungsanstalt rügt, die Vorinstanz habe zu Unrecht das ATSG für nicht anwendbar erklärt. Zum einen sehe das KVG im Bereich der Pflegefinanzierung nicht ausdrücklich eine Abweichung vom ATSG vor. Zum anderen sei die Rechtsprechung zur Differenzzahlungspflicht der Kantone nicht einschlägig. Das Bundesgericht habe zwar Streitigkeiten zwischen Versicherern und Kantonen nicht unter <ref-law> subsumiert, hingegen explizit offengelassen, ob im Rahmen von <ref-law> die verfahrensrechtliche Ordnung des ATSG zur Anwendung gelange (<ref-ruling> E. 5.5 S. 224). Die Pflegefinanzierung sei weder vom ATSG ausgenommen noch lege die Vorinstanz dar, weshalb das ATSG-Verfahren für die Beurteilung der damit zusammenhängenden Fragen nicht geeignet sein solle, was zugleich die Begründungspflicht verletze. Die Nichtanwendbarkeit des ATSG wäre mit vielen Nachteilen verbunden und nicht zuletzt sei die Pflegefinanzierung häufig verfahrensmässig mit den Ergänzungsleistungen gekoppelt, so dass ein Verfahrenssplitting für die Durchführungsstellen wie auch für die Betroffenen zu unhaltbaren Situationen führte. Das Gesetzgebungsverfahren lasse darauf schliessen, dass die Anwendbarkeit des ATSG auf die Pflegefinanzierung dem erklärten Willen des Gesetzgebers entsprochen habe. Den Kantonen komme überdies praktisch Versicherereigenschaft zu.
5. 5.1 Das KVG regelt - entsprechend seiner Verfassungsgrundlage (<ref-law>) - nicht das gesamte schweizerische Gesundheitswesen, sondern einzig die soziale Krankenversicherung (<ref-law>). Zwar waren unter der bis Ende 2010 geltenden Regelung ärztlich angeordnete Pflegemassnahmen in Pflegeheimen grundsätzlich Pflichtleistungen der obligatorischen Krankenpflegeversicherung (<ref-law> in der bis 31. Dezember 2010 gültig gewesenen Fassung) und unterstanden an sich dem Tarifschutz gemäss <ref-law>. Weil die festgelegten Tarife (aArt. 9a Abs. 2 KLV; in Kraft bis 31. Dezember 2010) nicht kostendeckend waren, wurde dieser Tarifschutz in der Praxis nicht voll umgesetzt, was zu einer unbefriedigenden und intransparenten Situation führte, welcher mit der Neuordnung der Pflegefinanzierung im Bundesgesetz vom 13. Juni 2008 über die Neuordnung der Pflegefinanzierung (AS 2009 3517 ff.) begegnet wurde. Die neuen Bestimmungen sollen einerseits die bisherige sozialpolitisch schwierige Situation vieler pflegebedürftiger Personen entschärfen, zugleich aber eine zusätzliche Belastung der obligatorischen Krankenpflegeversicherung verhindern. Deshalb wurde einerseits im Gesetz ausdrücklich festgelegt, dass die Krankenversicherung nicht die gesamten Pflegekosten übernimmt, sondern nur einen Beitrag daran leistet (<ref-law>). Anderseits begrenzte der Gesetzgeber aus sozialpolitischen Gründen die von den Heimbewohnern zu leistenden Pflegekosten betragsmässig (<ref-law>) und erleichterte zugleich für bedürftige Heimbewohner die Bezahlung dieser Pflegekosten durch eine Erhöhung der Ergänzungsleistungen (vgl. die Revision von Art. 10 und 11 ELG [SR 831.30] durch das Bundesgesetz über die Neuordnung der Pflegefinanzierung). Der verbleibende Betrag, der weder von der Krankenversicherung noch von den Bewohnern bezahlt wird, ist von der öffentlichen Hand (Kanton oder Gemeinden) zu übernehmen, was im Gesetz nicht klar gesagt, aber gemeint ist (Urteil 2C_864/2010 vom 24. März 2011 E. 4.2 mit zahlreichen Hinweisen). Für die Regelung der Restfinanzierung sind die Kantone zuständig (<ref-law>).
5.2 Die Restfinanzierung der Pflegekosten betrifft somit weder den Umfang der Grundversorgung noch die Leistungspflicht der Grundversicherung, sondern das Ausmass einer Vergütung, die nicht von der obligatorischen Krankenpflegeversicherung zu bezahlen ist. Leistungserbringer sind - je nach kantonaler Regelung - Kantone oder Gemeinden, also Personen öffentlichen Rechts, die grundsätzlich nicht dem KVG unterstellt sind, zumal sie ihre Leistungen nicht zu Lasten der obligatorischen Krankenpflegeversicherung abrechnen. Vor dem Hintergrund dieser Besonderheiten ist die beispielsweise im Kanton Thurgau statuierte, vom ATSG abweichende Verfahrensregelung zu sehen, welche das Departement für Finanzen und Soziales zur Beurteilung von Rekursen gegen Einspracheentscheide der kantonalen Ausgleichskasse als zuständig erklärt (§ 36 der Verordnung des Regierungsrates des Kantons Thurgau vom 20. Dezember 2011 zum Gesetz über die Krankenversicherung [RB 832.10]; ob die Kantone hiezu kompetent sind, wird offengelassen; E. 5.3 hienach).
5.3 Die Umsetzungsbestimmungen des Kantons St. Gallen zur Restfinanzierung der Pflegekosten enthalten weder eigene verfahrensrechtliche Regeln noch verweisen sie auf das ATSG. Ob die den Kantonen in <ref-law> eingeräumte Kompetenz, mit Blick darauf, dass im Bundesgesetz über die Pflegefinanzierung auf eine explizite Anwendbarkeitserklärung des ATSG verzichtet wurde, weil diese selbstverständlich sei (vgl. hiezu auch die Empfehlungen zur Umsetzung der Neuordnung der Pflegefinanzierung der Schweizerischen Konferenz der kantonalen Gesundheitsdirektorinnen und -direktoren vom 22. Oktober 2009, Vorbemerkung S. 3), sich auch auf das Verfahrensrecht erstreckt oder nur die Finanzierungsmodalitäten im engeren Sinn umfasst, braucht hier nicht abschliessend geprüft zu werden. Wie im Folgenden dargelegt wird, hält der vorinstanzliche Entscheid selbst dann nicht vor Bundesrecht stand, wenn von einer kantonalen Regelungskompetenz auszugehen wäre mit entsprechend eingeschränkter Kognition des Bundesgerichts (E. 1.2 hievor).
5.3 Die Umsetzungsbestimmungen des Kantons St. Gallen zur Restfinanzierung der Pflegekosten enthalten weder eigene verfahrensrechtliche Regeln noch verweisen sie auf das ATSG. Ob die den Kantonen in <ref-law> eingeräumte Kompetenz, mit Blick darauf, dass im Bundesgesetz über die Pflegefinanzierung auf eine explizite Anwendbarkeitserklärung des ATSG verzichtet wurde, weil diese selbstverständlich sei (vgl. hiezu auch die Empfehlungen zur Umsetzung der Neuordnung der Pflegefinanzierung der Schweizerischen Konferenz der kantonalen Gesundheitsdirektorinnen und -direktoren vom 22. Oktober 2009, Vorbemerkung S. 3), sich auch auf das Verfahrensrecht erstreckt oder nur die Finanzierungsmodalitäten im engeren Sinn umfasst, braucht hier nicht abschliessend geprüft zu werden. Wie im Folgenden dargelegt wird, hält der vorinstanzliche Entscheid selbst dann nicht vor Bundesrecht stand, wenn von einer kantonalen Regelungskompetenz auszugehen wäre mit entsprechend eingeschränkter Kognition des Bundesgerichts (E. 1.2 hievor).
5.4 5.4.1 Zunächst ergibt sich entgegen den vorinstanzlichen Erwägungen die Nichtanwendbarkeit der verfahrensrechtlichen Bestimmungen von <ref-law> im Bereich der Restfinanzierung von Pflegeleistungen nicht aus der Rechtsprechung zur - ebenfalls von den Kantonen zu übernehmenden - Differenzzahlungspflicht bei ausserkantonaler Spitalbehandlung gemäss <ref-law>. Das Bundesgericht hat in jenem Zusammenhang entschieden (<ref-ruling>), Zuständigkeit und Verfahren zur Geltendmachung und allfälligen gerichtlichen Durchsetzung auf kantonaler Ebene bleibe auch nach Inkrafttreten des ATSG weiterhin grundsätzlich Sache der Kantone (<ref-ruling> E. 6.3.2 S. 225 f.). Es erwog, die sozialversicherungsrechtliche Natur der Verpflichtung vermöge nichts daran zu ändern, dass die Kantone keine Versicherer im Sinne des KVG seien, so dass Streitigkeiten nach <ref-law> nicht unter <ref-law> fielen. Der Subventionscharakter der Kostenbeteiligungspflicht als versicherungsfremdes Element lasse die Kantone qualifiziert anders erscheinen als die Versicherer. Ob die verfahrensrechtliche Ordnung des ATSG anwendbar ist, liess das Bundesgericht offen (<ref-ruling> E. 5.5 S. 224). In einer weiteren Erwägung stellte es fest, bei Streitigkeiten zwischen Krankenversicherern und Kantonen betreffend die Differenzzahlungspflicht gemäss <ref-law> seien drei Verfahrensordnungen möglich: Nebst den Verfahrensvorschriften des ATSG käme das Verwaltungsverfahrensgesetz (VwVG) kraft <ref-law> oder (weiterhin) kantonales Recht in Frage.
5.4.2 Selbst wenn die den Kantonen in <ref-law> übertragene Regelungskompetenz auch das Verfahrensrecht umfassen würde (vgl. E. 5.3 hievor), spricht nach dem Gesagten nichts gegen eine kantonale Norm, welche die Anwendbarkeit der ATSG-Normen statuiert. In einigen Kantonen ist eine entsprechende Regelung denn auch Gesetz geworden (z.B. § 17 des Gesetzes des Kantons Luzern vom 31. September 2010 über die Finanzierung der Pflegeleistungen der Krankenversicherung [Pflegefinanzierungsgesetz; SRL 867] oder § 16 der Pflegefinanzierungsverordnung des Kantons Schwyz vom 3. November 2010 [SRS 361.511]; § 11 Abs. 1 der Verordnung des Kantons Aargau über die Umsetzung des Bundesgesetzes über die Neuordnung der Pflegefinanzierung vom 8. Dezember 2010 [SAR 301.213]).
5.5 Für die Anwendbarkeit des ATSG im Rahmen von <ref-law> sprechen mehrere überzeugende Gründe. Zunächst sind nach <ref-law> die Bestimmungen des ATSG auf die Krankenversicherung anwendbar, soweit das KVG nicht ausdrücklich eine Abweichung vorsieht. Unter den - allerdings nicht abschliessenden - Ausnahmen gemäss <ref-law> findet sich die Restfinanzierung der Pflegekosten nicht, zudem sieht das KVG diesbezüglich keine Abweichungen vom ATSG vor. Sodann sind keine Argumente ersichtlich (solche werden im angefochtenen Entscheid auch nicht angeführt), weshalb das Verfahrensrecht des ATSG für die Beurteilung von Ansprüchen nach <ref-law> nicht geeignet sein soll. Mit Blick auf die enge Verbindung der Ansprüche nach <ref-law> mit den Ergänzungsleistungen (EL), die sich verfahrensrechtlich nach dem ATSG richten, erscheint die Anwendbarkeit des ATSG vielmehr als sachgerecht: Nicht nur installierte das Bundesgesetz über die Neuordnung der Pflegefinanzierung mit der Restfinanzierung der stationären Langzeitpflege einen den EL vorgelagerten Kostenträger (mit entsprechender Entlastung der Pflegebedürftigen sowie auch der EL) und erhöhte die Vermögensfreibeträge mit entsprechender Erweiterung des Kreises der EL-Anspruchsberechtigten. Auch und vor allem stellt sich die Frage nach der Restfinanzierung von Pflegeleistungen häufig dann, wenn Ansprüche auf Ergänzungsleistungen ebenfalls im Raum stehen (vgl. auch E. 5.6 hienach). Für die (mutmasslich) Anspruchsberechtigten bedeutete es eine - vermeidbare - verfahrensrechtliche Erschwerung, wenn die beiden Ansprüche auf zwei unterschiedlichen Rechtswegen geltend zu machen wären.
5.6 Entscheidend ist aber der Wille des (kantonalen) Gesetzgebers. Nach dem erklärten Willen der Regierung des Kantons St. Gallen sollte der Aufwand für die Restfinanzierung möglichst gering gehalten werden, weshalb mit Blick darauf, dass "sich die Zuständigkeit des Kantons und seiner Gemeinden an den EL orientiert", eine EL-nahe Abwicklung sachgerecht scheine (Botschaft vom 22. Oktober 2007 zum Gesetz über die Pflegefinanzierung; Amtsblatt des Kantons St. Gallen Nr. 29 vom 19.Juli 2010 S. 2236). Aus diesem Grund wurde auf Gesetzesebene auch eine Zuständigkeit der kantonalen Sozialversicherungsanstalt begründet (Art. 10 Gesetz vom 13. Februar 2011 über die Pflegefinanzierung [sGS 331.2]). Im Bericht und Entwurf des Departementes des Innern und des Gesundheitsdepartementes vom 27. April 2010 zum Gesetz über die Pflegefinanzierung führten diese zum Verfahren wörtlich aus: "Nach <ref-law> kommen für das Verfahren grundsätzlich die Bestimmungen des ATSG zu Anwendung, wenn und soweit es die einzelnen Sozialversicherungsgesetze des Bundes vorsehen. <ref-law> erklärt die Bestimmungen des ATSG auf die Krankenversicherung als anwendbar, soweit das KVG nicht ausdrücklich eine Abweichung vorsieht. In Bezug auf die Neuregelung der Finanzierung nach Art. 25a nKVG sieht das KVG weder eine Abweichung vor, noch sind Bereiche als Ganzes ausdrücklich vom Geltungsbereich des ATSG ausgenommen. Damit sind auch die entsprechenden kantonalen Ausführungsbestimmungen grundsätzlich dem ATSG unterstellt. Unter diesen Umständen kann auf eine weitere Regelung im kantonalen Erlass verzichtet werden. Hingegen ist im neuen Gesetz aus Gründen der Transparenz die Regelung aufzunehmen, dass sich das Verfahren nach dem ATSG richtet, soweit der Erlass selbst keine Bestimmungen enthält." Ein "kostengünstiger, transparenter und einfacher Ablauf" namentlich unter Nutzung von Synergien mit den Ergänzungsleistungen entsprach nicht zuletzt mit Blick darauf, dass von den - damals - rund 6'000 im Kanton St. Gallen von der neuen Pflegefinanzierung betroffenen Personen rund 3'000 EL-Bezüger waren, auch den Intentionen der vorberatenden Kommission (Protokoll der Sitzung der vorberatenden Kommission vom 23. August 2010 S. 4 f.). Dass im Folgenden eine explizite Anwendbarkeit des ATSG nicht Eingang in das kantonale Recht fand - und verfahrensrechtlich überhaupt keine Regelung erlassen wurde -, ist vor dem Hintergrund zu sehen, dass der kantonale Gesetzgeber - in Übereinstimmung mit entsprechenden Informationen des Bundesamtes für Gesundheit - davon ausging, mit Blick auf die selbstverständliche Anwendbarkeit des ATSG bestehe kein kantonaler Regelungsbedarf (in diesem Sinne auch die letztinstanzlich aufgelegte Auskunft der Staatskanzlei St. Gallen vom 7. Juni 2010). Der angefochtene Entscheid widerspricht diesem gesetzgeberischen Willen, weshalb er unabhängig davon nicht geschützt werden kann, ob eine kantonale Kompetenz zur Verfahrensregelung im Bereich der Restfinanzierung von Pflegeleistungen besteht. Damit ist die Zuständigkeit des Versicherungsgerichts des Kantons St. Gallen zu bejahen und die Sache an dieses zum materiellen Entscheid zurückzuweisen.
6. Auf die Erhebung von Gerichtskosten wird umständehalber verzichtet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, der Entscheid des Versicherungsgerichts des Kantons St. Gallen vom 19. Januar 2012 aufgehoben und die Sache wird an das kantonale Gericht zurückgewiesen, damit es im Sinne der Erwägungen verfahre.
2. Es werden keine Gerichtskosten erhoben.
3. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons St. Gallen, dem Departement des Innern des Kantons St. Gallen und dem Kanton Wallis schriftlich mitgeteilt.
Luzern, 7. September 2012
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Meyer
Die Gerichtsschreiberin: Bollinger Hammerle