Sachverhalt:
A. Die 1939 geborene deutsche Staatsangehörige H._ hat Wohnsitz in Deutschland. Sie bezieht sowohl nach deutschem wie - zufolge zeitweiliger Erwerbstätigkeit in der Schweiz - nach schweizerischem Recht eine Altersrente (im November 2011: monatliche AHV-Rente von Fr. 155.-; monatliches deutsches Altersruhegeld in Höhe von EUR 353.29). Seit dem Jahre 2001 befindet sie sich in einem Pflegeheim in Deutschland und bezieht seit 13. Juli 2001 stationäre Hilfe zur Pflege nach dem zwölften Buch des deutschen Sozialgesetzbuches (SGB XII; Bescheinigung des Kreissozialamtes X._ vom 2. November 2011). Die AOK Gesundheitskasse, Bezirksdirektion Y._ (nachfolgend: AOK), lehnte - in Bestätigung einer Verfügung der AOK Z._ vom 1. Oktober 2007 - eine Aufnahme der H._ in die gesetzliche Krankenversicherung ab (Widerspruchsbescheid vom 26. November 2008). Bereits am 29. August 2007 hatte H._ die Helsana Versicherungen AG, Zürich (nachfolgend: Helsana), um Aufnahme in die obligatorische Krankenpflegeversicherung ersucht, was diese mit Verfügung vom 18. Dezember 2007 ablehnte. Nachdem H._ hiegegen Einsprache erhoben hatte, erliess die Helsana ein ebenfalls ablehnendes Verfügungsrektifikat vom 28. Januar 2008 (bestätigt mit Einspracheentscheid vom 30. Mai 2008).
B. H._ liess hiegegen Beschwerde erheben, welche das Sozialversicherungsgericht Basel-Stadt mit Entscheid vom 12. Juli 2011 guthiess; es hob den Einspracheentscheid vom 30. Mai 2008 auf und wies die Sache an die Helsana zurück zur Behandlung des Aufnahmegesuches im Sinne der Erwägungen.
C. Die Helsana führt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt die Aufhebung des angefochtenen Entscheides sowie die Einladung des Bundesamtes für Sozialversicherungen (BSV) zur Vernehmlassung.
H._ schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei; der Antrag auf Einladung des BSV zur Vernehmlassung sei abzuweisen und es sei ihr die unentgeltliche Rechtspflege zu gewähren.
Mit Verfügung vom 11. November 2011 weist das Bundesgericht das Gesuch um Nichteinladung des BSV zur Vernehmlassung ab und setzt diesem gleichzeitig Frist zur Einreichung einer solchen an. Die Vernehmlassung des Bundesamtes, mit welcher die Gutheissung der Beschwerde beantragt wird, geht am 19. Dezember 2011 beim Bundesgericht ein. Die Beschwerdegegnerin nimmt hiezu am 2. Februar 2012 Stellung.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzung gemäss Art. 95 und Art. 96 BGG erhoben werden. Das Bundesgericht prüft nach <ref-law> frei, ob der angefochtene Entscheid Bundesrecht verletzt, einschliesslich der von der Schweiz abgeschlossenen internationalen Verträge (<ref-ruling> E. 2; vgl. auch Markus Schott, in: Basler Kommentar, Bundesgerichtsgesetz, N. 50 ff. zu <ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat, es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 105 Abs. 2 bzw. <ref-law>).
2. 2.1 Streitig und zu prüfen ist, ob die Beschwerdeführerin die Beschwerdegegnerin ab 1. September 2007 rückwirkend in die obligatorische Krankenpflegeversicherung aufzunehmen hat. Unbestritten ist das Vorliegen eines grenzüberschreitenden Sachverhalts, der unter die Bestimmungen des am 1. Juni 2002 in Kraft getretenen Abkommens vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit fällt (FZA; SR 0.142.112.681).
2.2 Nach Art. 1 Abs. 1 des auf der Grundlage von Art. 8 FZA ausgearbeiteten und Bestandteil des Abkommens bildenden (Art. 15 FZA) Anhangs II ("Koordinierung der Systeme der sozialen Sicherheit") FZA in Verbindung mit Abschnitt A dieses Anhangs waren bis 31. März 2012 (u.a.) die Verordnung (EWG) Nr. 1408/71 des Rates vom 14. Juni 1971 zur Anwendung der Systeme der sozialen Sicherheit auf Arbeitnehmer und Selbstständige sowie deren Familienangehörige, die innerhalb der Gemeinschaft zu- und abwandern massgeblich (SR 0.831.109.268.1; sog. Wanderarbeitnehmerverordnung; nachfolgend: VO 1408/71). Ziel der VO 1408/71 ist es, grösstmögliche Freizügigkeit der Arbeitnehmerinnen und Arbeitnehmer herzustellen. Dieses wird verfehlt, wenn Arbeitnehmende, die von ihrem Freizügigkeitsrecht Gebrauch machen, Vergünstigungen der sozialen Sicherheit verlieren (Urteil des EuGH vom 8. März 2001, Jauch, Rs C-215/99, Slg. 2001, I-1901, Randnr. 20).
2.3 Rentnerinnen und Rentner, die nach den Rechtsvorschriften eines oder mehrerer Mitgliedstaaten zum Bezug einer Rente berechtigt sind, fallen aufgrund ihrer Zugehörigkeit zu einem System der sozialen Sicherheit auch dann unter die Bestimmungen der VO 1408/71 über die Arbeitnehmer, wenn sie keine Erwerbstätigkeit ausüben, soweit auf sie keine besonderen Bestimmungen anzuwenden sind (Urteil des EuGH vom 30. Juni 2011, da Silva Martins, Rs C-388/09, Randnr. 37). Art. 28 VO 1408/71 regelt den Rentenanspruch auf Grund der Rechtsvorschriften eines einzigen oder mehrerer Staaten, falls ein Anspruch auf Leistungen im Wohnland nicht besteht und bestimmt (u.a.), dass ein Rentner, der nach den Rechtsvorschriften von zwei Mitgliedstaaten zum Bezug von Renten berechtigt ist ("Doppelrentner") und der keinen Anspruch auf Leistungen nach den Rechtsvorschriften des Wohnsitzstaates hat, diese Leistungen nach den Rechtsvorschriften des anderen rentenausrichtenden Staates erhält, wenn bei Wohnsitz in jenem Staat ein entsprechender Anspruch bestünde. Diese Norm ist auch für die Versicherungspflicht in der Krankenversicherung massgeblich (ad Schweiz Abs. 3 Bst. a Ziff. ii Anhang VI VO 1408/71). Indes schliesst Art. 4 Abs. 4 der VO 1408/71, welcher den sachlichen Geltungsbereich regelt, die Sozialhilfe von ihrem Anwendungsbereich aus.
2.4 Zu prüfen ist daher, ob die der Beschwerdegegnerin gestützt auf das SGB XII (§§ 47-52) gewährte Hilfe bei Krankheit als Sozialhilfe oder als Leistung der sozialen Sicherheit zu qualifizieren ist. Sind die der Beschwerdegegnerin zugesprochenen Leistungen als Sozialhilfe zu qualifizieren, fallen sie nicht in den Anwendungsbereich der VO 1408/71 und sind somit auch nicht als Leistungen im Krankheitsfall aufzufassen. Weil nach deutschem Recht Sozialhilfebezügerinnen und -bezüger von der Aufnahme in die gesetzliche Krankenversicherung ausgeschlossen sind (vgl. § 264 des Fünften Buches des deutschen Sozialgesetzbuches [SGB V]; sowie Urteil des deutschen Bundessozialgerichts [BSG] vom 17. Juni 2008, B1 KR 30/07, Randnr. 16), hätte die Qualifikation der Leistungen gemäss SGB XII als Sozialhilfe einen Anspruch auf Aufnahme in die schweizerische obligatorische Krankenpflegeversicherung zur Folge. Andernfalls, d.h. wenn die Hilfe bei Krankheit eine Leistung der sozialen Sicherheit bei Krankheit darstellt, fällt eine Aufnahme in die schweizerische Krankenversicherung nach Art. 28 VO 1408/71 ausser Betracht.
3. 3.1 Das kantonale Gericht erwog unter Bezugnahme auf die Lehrmeinung von Maximilian Fuchs (Europäisches Sozialrecht, 3. Aufl. 2005), die Hilfe in besonderen Lebenslagen und damit namentlich auch die Krankenhilfe sei eine nach Art. 4 Abs. 4 VO 1408/71 vom Anwendungsbereich der VO 1408/71 ausgeschlossene Leistung der Sozialhilfe. Die formale Gleichheit und Zweckrichtung im Hinblick auf bestimmte Risiken mache die Sozialhilfeleistung noch nicht zu einer solchen der sozialen Sicherheit. Die der vorinstanzlichen Beschwerdeführerin nach deutschem Recht gewährten Leistungen fielen, da sozialhilferechtlich ausgestaltet, nicht in den Anwendungsbereich von Art. 4 VO 1408/71. Zudem stehe - gemäss rechtskräftig gewordenem Widerspruchsentscheid der AOK vom 26. November 2008 und Schreiben der AOK vom 31. März 2010 - fest, dass eine Aufnahme in die gesetzliche Krankenversicherung des Wohnlandes Deutschland ausgeschlossen sei, weshalb eine schweizerische Krankenversicherungspflicht bestehe.
3.2 Die Beschwerdeführerin macht namentlich geltend, selbst wenn die bei Krankheit nach SGB XII gewährten Leistungen Bedarfselemente aufwiesen, müssten sie als Leistungen der sozialen Sicherheit i.S.d. VO 1408/71 qualifiziert werden. Die Beschwerdegegnerin habe Anspruch auf die gleichen Leistungen im Krankheitsfall wie die in Deutschland gesetzlich versicherten Personen. Der deutsche Gesetzgeber habe eine allgemeine Versicherungspflicht für alle Personen mit Wohnsitz in Deutschland angestrebt. Leistungsempfänger nach SGB XII seien, trotz fehlender Krankenversicherungsunterstellung in Deutschland, für das Risiko Krankheit adäquat, d.h. gleichermassen wie die gesetzlich Unterstellten versichert, weshalb kein Raum für die Anwendung von Art. 28 VO 1408/71 bleibe.
3.3 Das BSV führt aus, die Beschwerdegegnerin habe Anspruch auf Leistungen bei Krankheit gemäss den Rechtsvorschriften ihres Wohnsitzlandes Deutschland. Entsprechend finde Art. 27 VO 1408/71 Anwendung, d.h. ein Leistungsanspruch am Wohnort; eine Versicherungspflicht gemäss KVG falle ausser Betracht. Dass Personen, welche nebst einer deutschen Rente Leistungen nach SGB XII beziehen, weiterhin von der Versicherungspflicht in der gesetzlichen Krankenversicherung ausgenommen seien, stelle eine Lücke im nationalen deutschen Sozialversicherungsrecht dar, welche nicht unter Anwendung der koordinationsrechtlichen Bestimmung von Art. 28 VO 1408/71 gefüllt werden könne. Es wäre stossend und schwer nachvollziehbar, wenn die Schweiz verpflichtet würde, die sich aus dem deutschen Recht ergebende Lücke zu füllen, die tendenziell schlechtere Risiken umfasse. Sodann widerspräche es Sinn und Zweck der VO 1408/71, wenn Mitgliedstaaten durch entsprechende Ausgestaltung der nationalen Regelungen ihre Leistungspflicht bei Mehrfachrentnern ausschliessen könnten. Schliesslich würde das in Anhang VI zur VO 1408/71 vorgesehene Optionsrecht (wonach Personen mit Wohnsitz in Deutschland sich von der Schweizer Krankenversicherungspflicht befreien lassen können) seines Sinnes entleert, wenn sie später als (Mehrfach-)Rentner von der Solidarität in der schweizerischen Krankenversicherung profitieren könnten.
4. 4.1 Nach der Rechtsprechung des EuGH hängt die Unterscheidung zwischen Sozialhilfe und Leistungen der sozialen Sicherheit von verschiedenen Kriterien ab. Grundsätzlich wird die Sozialhilfe einschränkend interpretiert, während der sozialen Sicherheit "der weitestmögliche Anwendungsbereich" einzuräumen ist (Schrammel/Winkler, Europäisches Sozialrecht, 2010, S. 246 f.). Diese Absicht wurde unterstrichen, als im Jahre 1992 mit Art. 4 Abs. 2a VO 1408/71 deren Anwendungsbereich auf sog. beitragsunabhängige Sonderleistungen und damit auf Leistungen ausgedehnt wurde, die sowohl Elemente der Sozialhilfe wie auch der sozialen Sicherheit enthalten ("Mischleistungen"). Seither können namentlich auch solche Leistungen in den Anwendungsbereich der VO 1408/71 fallen, die einem der in Art. 4 Abs. 1 VO 1408/71 aufgeführten Zweige der sozialen Sicherheit entsprechen, indes bis dahin, etwa wegen ihrer Einkommensabhängigkeit, als Leistungen der Sozialhilfe von der VO 1408/71 ausgenommen waren (Urteile des EuGH vom 8. März 2001, Jauch, Rs C-215/99, Slg. 2001, I-1901, sowie vom 2. August 1993, Acciardi, Rs C-66/92, Slg. 1993, I-4567; Silvia Bucher, Soziale Sicherheit, beitragsunabhängige Sonderleistungen und soziale Vergünstigungen, Diss. Freiburg 2000, S. 46 Rz. 102). Entscheidend für die Zuordnung zur sozialen Sicherheit oder zur Sozialhilfe sind insbesondere die Zielsetzungen und die Voraussetzungen der Leistungsgewährung; nicht ins Gewicht fällt dagegen die Qualifikation im nationalen Recht (z.B. Urteil des EuGH vom 5. März 1998, Molenaar, Rs C-160/96, Slg. 1998, I-843; Schrammel/Winkler, a.a.O., S. 246; Jürgen Beschorner, Die beitragsunabhängigen Geldleistungen i.S.v. Art. 4 Abs. 2a VO [EWG] Nr. 1408/71 in der Rechtsprechung des EuGH, in: ZESAR 08/09, S. 323). So entschied der Gerichtshof beispielsweise im Urteil Hosse vom 21. Februar 2006 (Rs C-286/03, Slg. 2006. I-1771 Randnr. 38), dass Leistungen, die objektiv aufgrund eines gesetzlich umschriebenen Tatbestandes gewährt werden und die darauf abzielen, den Gesundheitszustand und die Lebensbedingungen der Pflegebedürftigen zu verbessern, im Wesentlichen eine Ergänzung der Leistungen der Krankenversicherung bezwecken und damit als "Leistungen bei Krankheit" im Sinne von Art. 4 Abs. 1 lit. a VO 1408/71 zu betrachten sind. Mit Urteil vom 20. Juni 1991, Newton, Rs C-356/89, Slg. 1991, I-3035, entschied der EuGH, eine Beihilfe für Behinderte falle in den Bereich der sozialen Sicherheit und sei damit vom Anwendungsbereich der VO 1408/71 grundsätzlich erfasst, wenn die Empfängerin oder der Empfänger nach dem persönlichen Geltungsbereich der nationalen Vorschriften dem Bereich der sozialen Sicherheit zuzuordnen ist. Grosse Bedeutung hat nach der Rechtsprechung des EuGH für die Zugehörigkeit einer Leistung zur sozialen Sicherheit, ob sie ohne jede im Ermessen liegende individuelle Prüfung der persönlichen Bedürftigkeit den Begünstigten aufgrund eines gesetzlich umschriebenen Tatbestands gewährt wird (vgl. u. a. Urteil des EuGH vom 27. März 1985, Hoeckx, Rs 249/83, Slg. 1985 S. 973, Randnrn. 12 bis 14; Urteil des EuGH vom 18. Juli 2006, De Cuyper, Rs C-406/04, Slg. 2006, I-6971, Randnr. 23; Urteil des EuGH vom 11. Juni 1991, Frankreich, Rs C-307/89, Slg. 1991 S. I-2903, Randnr. 10; Bucher, a.a.O., Randnr. 96; Schrammel/Winkler, a.a.O., S. 247). Auch gemäss dem Leitfaden des BSV für die Durchführung des FZA, Ausgabe 4/07, kann eine Leistung nur unter der Voraussetzung der sozialen Sicherheit zugeordnet werden, dass "sie unter objektiven und rechtlich festgelegten Voraussetzungen gewährt wird, ohne dass die zuständige Behörde sonstige persönliche Verhältnisse berücksichtigen darf".
4.2 Die gestützt auf SGB XII gewährten Leistungen bei Krankheit unterscheiden sich inhaltlich nicht von den Ansprüchen in der gesetzlichen Krankenversicherung. Nicht nur sind es die (gesetzlichen) Krankenversicherungen, welche die Krankenbehandlung von Sozialhilfeempfängern erbringen (und zwar aufgrund eines gesetzlichen Auftrages im Sinne von § 93 des Zehnten Buches des deutschen Sozialgesetzbuches [SGB X]; Urteil des BSG vom 17. Juni 2008, B1 KR 30/07R, Randnr. 15 m.w.H.; § 52 SGB XII). Auch leistungsrechtlich besteht Gleichheit: § 264 SGB V überträgt den Krankenkassen in Abstimmung mit dem SGB XII die grundsätzlich den Sozialhilfeträgern obliegende Aufgabe zur Gewährung der den Regelungen der gesetzlichen Krankenversicherung entsprechenden Leistungen (BSG, a.a.O., Randnr. 13). Die Hilfeempfänger haben Anrecht auf die Ausstellung einer Krankenversicherungskarte nach § 261 SGB V (Christian Grube/Volker Wahrendorf, SGB XII, Sozialhilfe, Kommentar, 2005, N. 20 zu § 48). Nach der Rechtsprechung des BSG bleibt die Hilfe bei Krankheit gleichwohl "dem Grunde nach" eine Aufgabe der Sozialhilfe und die Sozialhilfebezüger gelten nicht als gesetzlich versichert (BSG, a.a.O., Randnr. 12). Hintergrund dieser Rechtslage ist, dass eine Gleichstellung von Empfängern laufender Hilfe zum Lebensunterhalt und von Hilfen in besonderen Lebenslagen zunächst wegen politischer Uneinigkeit über angemessene Beitragszahlungen nicht verwirklicht werden konnte und dass mit der Neuregelung von § 264 SGB V (in Kraft getreten am 1. Januar 2004; vgl. auch E. 4.4 hienach) an die Stelle der ursprünglich vorgesehenen Mitgliedschaft in der gesetzlichen Krankenversicherung (nur, aber immerhin) eine leistungsrechtliche Gleichstellung der Sozialhilfeempfänger mit den gesetzlich krankenversicherten Personen trat, dies ohne volle Mitgliedschaftsrechte der Sozialhilfeempfänger (Urteil BSG, a.a.O., Randnr. 16, mit Hinweis auf den Gesetzesentwurf der Fraktionen SPD, CDU/CSU und Bündnis 90/Die Grünen, Deutscher Bundestag Drucksache 15/1525, S. 140, rechte Spalte zu Art. 1 Nr. 152 - § 264). Ungeachtet des fehlenden Mitgliedschaftsrechts in der gesetzlichen Krankenversicherung weisen die Leistungen gemäss § 48 SGB XII indes einen klaren Bezug zur Krankheit auf und damit zu einem der von Art. 4 Abs. 1 VO 1408/71 erfassten Risiken, so dass ein (Haupt-)Kriterium für die Qualifikation als Leistung der sozialen Sicherheit erfüllt ist (vgl. Bucher, a.a.O. Randnr. 96).
4.3 Die der Beschwerdegegnerin gewährte Hilfe bei Krankheit enthält aber auch Elemente der Sozialhilfe. Namentlich findet sich ihre Rechtsgrundlage im SGB XII und damit im Recht der - steuerfinanzierten, beitragsunabhängigen - Sozialhilfe. Nach § 2 SGB XII wird Sozialhilfe nur Personen gewährt, die sich nicht durch Einsatz ihrer Arbeitskraft, ihres Einkommens und ihres Vermögens selbst helfen können oder welche die erforderliche Leistung nicht von anderen, insbesondere von Angehörigen oder von Trägern anderer Sozialleistungen, erhalten. § 9 Abs. 1 SGB XII bestimmt, dass sich die Leistungen "nach der Besonderheit des Einzelfalles, insbesondere nach der Art des Bedarfs, den örtlichen Verhältnissen, den eigenen Kräften und Mitteln der Person oder des Haushalts bei der Hilfe zum Lebensunterhalt" richten. Die Berücksichtigung der Besonderheiten des Einzelfalles unterscheidet die Sozialhilfe wesentlich von anderen Bereichen des Sozialrechts, die eine weitgehend pauschalierte Leistungsgewährung vorsehen (vgl. zum Ganzen: Bernd-Günter Schwabe, Sozialhilfe, 17. Aufl. 2007, S. 122). Aus der nationalrechtlichen Zuordnung allein kann indessen nach dem Gesagten (E. 4.1 hievor) noch nicht geschlossen werden, dass es sich um Sozialhilfeleistungen i.S.v. Art. 4 Abs. 4 VO 1408/71 handelt.
4.4 Die Hilfe bei Krankheit nach § 48 SGB XII umfasst nach den bisherigen Ausführungen sowohl Wesensmerkmale der sozialen Sicherheit (sie betrifft das Risiko Krankheit; leistungsmässig besteht Gleichheit mit der gesetzlichen Krankenversicherung) als auch solche der Sozialhilfe (wo sich ihre Rechtsgrundlage findet; zudem sind die Leistungen beitragsunabhängig und steuerfinanziert); es kommt ihr ein sog. Mischcharakter zu. Die Behandlung solcher Leistungen namentlich auch in der Rechtsprechung des EuGH ruft mitunter grosse Schwierigkeiten und Abgrenzungsprobleme hervor (vgl. Beschorner, a.a.O., S. 323), die der EuGH bisher häufig in Anwendung einer weiten Auslegung der sozialen Sicherheit entschied (E. 4.1 hievor). Nähern sich nationale Rechtsvorschriften durch einige Merkmale der Sozialhilfe an, indem sie beispielsweise die Bedürftigkeit als wesentliche Voraussetzung statuieren und keine Berufstätigkeits-, Mitgliedschafts- oder Beitragszeiten voraussetzen, können darauf basierende Leistungen unter Umständen gleichwohl als solche der sozialen Sicherheit qualifiziert werden (Bucher, a.a.O., S. 53 Rz. 117 ff. mit zahlreichen Hinweisen auf Urteile des EuGH). Die Rechtsprechung des EuGH zur Qualifizierung solcher Mischleistungen ist sodann stark einzelfallbezogen (vgl. E. 4.1 hievor) und wird namentlich auch von den Folgen inspiriert, welche die Zuordnung einer Leistung nach sich zieht (vgl. Bucher, a.a.O., S. 79 Rz. 182). Bei Leistungen mit Mischcharakter neigt der EuGH dazu, den materiellen Charakter der Leistung heranzuziehen (Beschorner, a.a.O.).
4.5 Die konkreten Konsequenzen einerseits und der materielle Charakter der Leistung anderseits sind auch bei der Beurteilung der der Beschwerdegegnerin zugesprochenen Hilfe bei Krankheit zu berücksichtigen. Dabei fällt insbesondere ins Gewicht, dass die Bedürftigkeit zwar zweifellos anspruchsbegründendes Element für den Leistungsbezug in der Sozialhilfe ist (E. 4.3 hievor), dass sich indes die aufgrund von § 48 SGB XII zugesprochenen Leistungen nach dem gesetzlichen Krankenversicherungsrecht richten (E. 4.2 hievor). Sie werden demzufolge aufgrund einer gesetzlich umschriebenen Stellung und unter objektiven, rechtlich festgelegten Voraussetzungen gewährt. Der Rechtsumstand, dass die Leistungen bei Krankheit von Personen, welche bei Inkrafttreten des Gesetzes zur Modernisierung der gesetzlichen Krankenversicherung (GMG; BGBl I 2003, S. 2190) am 1. Januar 2004 Sozialhilfe bezogen und die daher von der Mitgliedschaft in der gesetzlichen Krankenversicherung ausgeschlossen blieben, durch den Sozialhilfeträger finanziert werden (zu den Gründen E. 4.2 hievor), rechtfertigt es nicht, diese Leistungen als Sozialhilfe im Sinne von Art. 4 Abs. 4 VO 1408/71 zu qualifizieren und ihnen demzufolge den Charakter als Leistungen bei Krankheit nach Art. 28 Abs. 1 VO 1408/71 abzusprechen. Die Nähe zu den Leistungen der sozialen Sicherheit bei Krankheit ist in Würdigung aller Umstände deutlich grösser als das Gewicht der sozialhilferechtlichen Elemente. Es wäre schliesslich rechtlich nicht überzeugend, wenn die Beschwerdegegnerin einzig deswegen, weil ihr als Sozialhilfebezügerin wegen der Eigenheit der nationalrechtlichen Bestimmungen kein Mitgliedschaftsrecht in der deutschen gesetzlichen Krankenversicherung zusteht, bessergestellt wäre als die übrigen deutsch-schweizerischen Doppelrentner mit Wohnsitz in Deutschland, welche keine Sozialhilfe beziehen, ebenfalls in der gesetzlichen Krankenversicherung versichert sind - somit einen der Beschwerdegegnerin identischen Anspruch auf Leistungen bei Krankheit haben -, die sich aber nicht nach Art. 28 VO 1408/71 in der schweizerischen Krankenversicherung versichern können. Die Beschwerde ist begründet.
5. Die Beschwerdegegnerin ist offensichtlich bedürftig, weshalb ihr die unentgeltliche Rechtspflege (Prozessführung und Verbeiständung) zu gewähren ist (<ref-law>). Aufgrund ihrer prozessualen Stellung als Beschwerdegegnerin brauchen die Prozessaussichten nicht geprüft zu werden. Sie hat jedoch der Gerichtskasse Ersatz zu leisten, sofern sie später dazu in der Lage ist (<ref-law>).
6. Das Verfahren ist kostenpflichtig. Die unterliegende Beschwerdegegnerin hat die Gerichtskosten zu tragen (<ref-law>). Zufolge Gewährung der unentgeltlichen Rechtspflege werden diese einstweilen auf die Gerichtskasse genommen. Die obsiegende Beschwerdeführerin kann keine Parteientschädigung beanspruchen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der Entscheid des Sozialversicherungsgerichts des Kantons Basel-Stadt vom 12. Juli 2011 wird aufgehoben.
2. Der Beschwerdegegnerin wird die unentgeltliche Rechtspflege gewährt.
3. Die Gerichtskosten von Fr. 500.- werden der Beschwerdegegnerin auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4. Rechtsanwalt lic. iur. Robert Karrer, Reinach BL, wird als unentgeltlicher Anwalt der Beschwerdegegnerin bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2500.- ausgerichtet.
5. Das Sozialversicherungsgericht des Kantons Basel-Stadt wird über eine Neuverlegung der Parteikosten für das kantonale Verfahren entsprechend dem Ausgang des letztinstanzlichen Prozesses zu befinden haben.
6. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht Basel-Stadt, dem Bundesamt für Gesundheit und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 12. April 2012
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Meyer
Die Gerichtsschreiberin: Bollinger Hammerle