Sachverhalt:
A. Mit Verfügung vom 9. September 2010 stellte die Ausgleichskasse Appenzell Ausserrhoden die Witwerrente des 1953 geborenen B._ auf den 30. November 2010 ein, weil seine jüngste Tochter im November 2010 das 18. Altersjahr vollendet habe und damit seine Anspruchsberechtigung erloschen sei.
B. Die hiegegen erhobene Beschwerde des B._ wies das Obergericht des Kantons Appenzell Ausserrhoden mit Entscheid vom 22. Juni 2011 ab.
C. B._ beantragt vor Bundesgericht, der angefochtene Entscheid sei aufzuheben und die Ausgleichskasse sei anzuweisen, ihm auch nach dem 1. Dezember 2010 die Witwerrente "bis auf weiteres" auszurichten.
Am 8. September 2011 ersucht B._ um Gewährung der unentgeltlichen Prozessführung und Verbeiständung.
Vorinstanz und Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung. Die Ausgleichskasse schliesst auf Abweisung der Beschwerde.

Erwägungen:
1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann namentlich eine Verletzung von Bundesrecht, Völkerrecht und kantonalen verfassungsmässigen Rechten gerügt werden (<ref-law>). Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (<ref-law>).
2. Nach <ref-law> erlischt der Anspruch auf eine Witwerrente, zusätzlich zu den in <ref-law> aufgezählten Gründen (Wiederverheiratung bzw. Tod der Witwe oder des Witwers), wenn das letzte Kind des Witwers das 18. Altersjahr vollendet hat.
2.1 Die Vorinstanz erwog, der Wortlaut von <ref-law> sei eindeutig, eine Interpretation daher weder nötig noch zulässig. Gleichwohl sei ein Blick in die Materialien aufschlussreich und erhelle, dass der Gesetzgeber die unterschiedliche Behandlung von Witwen und Witwern bewusst in Kauf genommen und als vertretbar erachtet habe. Kein Auslegungsbedarf ergebe sich auch aus dem Normsinn. Dem Gericht stehe es nicht zu, den klaren Gesetzeswortlaut zu negieren (<ref-law>), die Beschwerde sei daher abzuweisen.
2.2 Der Beschwerdeführer rügt eine Verletzung von Art. 14 in Verbindung mit Art. 8 EMRK. Er bringt vor, das Landesrecht sei zunächst konventionskonform auszulegen; wo dies nicht möglich sei, komme den Garantien der EMRK Vorrang vor innerstaatlichem Recht zu. Nach der auch für die Schweizer Behörden massgeblichen Rechtsprechung des Europäischen Gerichtshofes für Menschenrechte (EGMR) zu Art. 14 in Verbindung mit Art. 8 EMRK verstosse die Nichtausrichtung einer Hinterlassenenleistung an Witwer gegen Art. 14 EMRK in Verbindung mit Art. 1 des (von der Schweiz nicht ratifizierten) ersten Zusatzprotokolls zur EMRK vom 20. März 1952 (nachfolgend 1. ZP EMRK). Die Rechte aus dem EMRK-geschützten Familienleben würden mit der Volljährigkeit der Kinder nicht automatisch erlöschen. Gewichtige Gründe für die in <ref-law> enthaltene geschlechtsbedingte Ungleichbehandlung fehlten. Eine Privilegierung der Witwen gegenüber den Witwern sei deshalb nicht gerechtfertigt, zumal das im Rahmen der 20. (recte: 10.) AHV-Revision angeführte gesetzgeberische Argument der Seltenheit von Hausmannsehen nicht sachgerecht sei. Ein Wiedereinstieg in das Berufsleben falle ihm schon altershalber ausserordentlich schwer, ein solcher sei auch unzumutbar.
3. 3.1 Mangels Ratifizierung des 1. ZP EMRK ist die hierauf beruhende Rechtsprechung des EGMR zur diskriminierungsfreien Gewährung von Sozialleistungen für die Schweiz nicht verbindlich. Die gestützt auf Art. 14 in Verbindung mit Art. 8 EMRK ergangenen Urteile des EGMR zur diskriminierungsfreien Gewährung von Sozialleistungen, die der Förderung der Familie dienen oder deren Organisation betreffen, haben Gesetzgeber und Gerichte hingegen zu beachten (vgl. Edgar Imhof, Die Bedeutung menschenrechtlicher Diskriminierungsverbote für die Soziale Sicherheit, Jusletter 7. Februar 2005, Rz. 22). Das akzessorische Diskriminierungsverbot von Art. 14 EMRK verbietet Unterscheidungen aufgrund bestimmter Merkmale bei der Umsetzung von in der EMRK garantierten Rechten und Freiheiten. Es kann immer schon dann angerufen werden, wenn der umstrittene Sachverhalt in den Schutzbereich einer konventionsrechtlichen Garantie fällt; deren Verletzung ist nicht erforderlich (Urteil des EGMR, Willis gegen das Vereinigte Königreich, vom 11. Juni 2002, Rs Nr. 36042/97, Rz. 29; <ref-ruling> E. 3.3.3 S. 128). Nicht jede unterschiedliche Behandlung ist diskriminierend. Eine verpönte Ungleichbehandlung setzt voraus, dass vergleichbare Situationen aufgrund von Rasse, Hautfarbe, Geschlecht, nationaler oder sozialer Herkunft usw. unterschiedlich behandelt werden, ohne dass sich dies objektiv und sachlich rechtfertigen lässt. Die umstrittene Massnahme muss aber mit Blick auf den verfolgten Zweck zulässig erscheinen und die zu dessen Realisierung eingesetzten Mittel müssen verhältnismässig sein (BGE a.a.O.).
3.2 Im Urteil 9C_521/2008 vom 5.Oktober 2009 befasste sich das Bundesgericht mit dem Anspruch auf Witwerrente eines Mannes, der in eingetragener gleichgeschlechtlicher Partnerschaft gelebt hatte und dessen Partner kurz nach Registrierung der Gemeinschaft verstorben war. Auch in jenem Fall rügte der Beschwerdeführer, Art. 23 und 24 AHVG seien diskriminierend; sie verstiessen gegen Art. 6 Abs. 1 und 14 EMRK. Das Bundesgericht wies auf die Rechtsprechung des EGMR hin, wonach Art. 14 EMRK keine eigenständige Bedeutung zukommt und dieser nur zusammen mit konventionsgeschützten Ansprüchen zur Anwendung gelangt (E. 3.1 hievor). Es erwog, Art. 6 EMRK garantiere das Recht auf Zugang zu einem Gericht, schaffe aber keinen gegenüber dem Staat durchsetzbaren Anspruch auf sozialversicherungsrechtliche Leistungen. Weil das Recht auf Zusprechung einer Witwerrente nicht in den Anwendungsbereich von Art. 6 EMRK falle, bleibe auch kein Raum für den Beizug von Art. 14 EMRK, dessen Garantien im Übrigen nicht über <ref-law> hinausgingen (BGer a.a.O., E. 4.3).
3.3 Nach der Rechtsprechung des EGMR lässt sich aus Art. 8 EMRK keine Pflicht der Mitgliedstaaten ableiten, bestimmte Sozialversicherungsleistungen zu erbringen (betreffend Karenzurlaubsgeld: Urteil Petrovic c. Österreich vom 27. März 1998, Rep. l998-II 579, Rz. 26; vgl. auch Urteil Chapman c. Vereinigtes Königreich vom 18. Januar 2001, Rs 27238/95, Rz. 98 f.; Cordula Dröge/Thilo Marauhn, Soziale Grundrechte in der Europäischen Grundrechtscharta - aus der Perspektive der EMRK, in: Soziale Grundrechte in der Europäischen Union, 2000, S. 90 f.). Art. 8 EMRK begründet somit auch keinen (direkten) Anspruch des überlebenden Ehemannes auf eine Witwerrente der Alters- und Hinterlassenenversicherung. Die vom Beschwerdeführer geltend gemachten Ansprüche sind (materiellrechtlich) nach <ref-law> zu beurteilen, wonach ein Anspruch auf Witwerrente erlischt, wenn das letzte Kind des Witwers das 18. Altersjahr vollendet hat (E. 2 hievor). Zu prüfen ist allerdings, ob diese Bestimmung eine verpönte Diskriminierung aufgrund der Geschlechtszugehörigkeit enthält.
3.4 Mit der Annahme von Art. 4 Abs. 2 aBV (seit 1. Januar 2000: <ref-law>) hat der Verfassungsgeber autoritativ festgestellt, dass die Zugehörigkeit zum einen oder andern Geschlecht grundsätzlich keinen rechtserheblichen Aspekt darstellt. Mann und Frau haben somit für die ganze Rechtsordnung im wesentlichen als gleich zu gelten. Das Bundesgericht hat daher wiederholt erklärt, seit dem Inkrafttreten von Art. 4 Abs. 2 aBV sei es dem kantonalen wie auch dem eidgenössischen Gesetzgeber grundsätzlich verwehrt, Normen zu erlassen, welche Mann und Frau ungleich behandeln; die erwähnte Verfassungsbestimmung schliesse die Geschlechtszugehörigkeit als taugliches Kriterium für rechtliche Differenzierungen aus (z.B. <ref-ruling> E. 7.1 S. 136 mit Hinweisen). Eine unterschiedliche Behandlung von Mann und Frau sei nur noch zulässig, wenn auf dem Geschlecht beruhende biologische oder funktionale Unterschiede eine Gleichbehandlung absolut ausschlössen (<ref-ruling> E. 5a S. 29 und seitherige Rechtsprechung). Der Vorbehalt funktionaler Unterschiede in der bundesgerichtlichen Rechtsprechung - biologische Unterschiede fallen vorliegend zum vornherein ausser Betracht - bedeutet insbesondere nicht, dass überkommenen Rollenverständnissen, so sie denn heute noch der Realität entsprechen, ohne weiteres auch in Zukunft rechtliche Relevanz verliehen werden dürfte (vgl. schon Jörg Paul Müller/Stefan Müller, Grundrechte, Besonderer Teil, 1985, S. 200; Beatrice Weber-Dürler, Auf dem Weg zur Gleichberechtigung, in ZSR NF 104 [1985] I S. 13 f.)
3.5 Der gesetzlichen Regelung des Anspruchs auf eine Witwerrente liegt die Überlegung zu Grunde, der Ehemann komme im Allgemeinen für den Lebensunterhalt der Ehefrau auf. Er wird daher vom Recht als Versorger, die Ehefrau namentlich bei Vorhandensein von Kindern (vgl. <ref-law>) als Versorgte vorausgesetzt, weshalb die Witwe in der Regel eine Witwenpension oder Witwenrente erhält während ein Korrelat für den Witwer weitgehend fehlt. Eine geschlechtsneutrale Regelung würde indes nicht an den Geschlechtsunterschied anknüpfen, sondern an die Frage, ob jemand (Mann oder Frau) den Versorger verloren habe (vgl. Weber-Dürler, a.a.O.). Der Bundesrat schlug im Rahmen der 10. AHV-Revision die Einführung eines beschränkten Witwerrentenanspruches in der AHV vor (BBl 1990 II 37 f., 155 f.). Die Räte entschieden sich für die bis heute gültig gebliebene Regelung, wonach die verwitwete Frau selbst dann in den Genuss der Witwenrente kommt, wenn sie zu keinem Zeitpunkt auf die Erfüllung der zivilrechtlichen Unterhaltspflicht gemäss altem Eherecht durch den Ehegatten angewiesen war, während das gleiche Recht auf Hinterlassenenrente dem verwitweten Ehemann nicht zugestanden wird. Dass dies eine unzulässige, Art. 4 Abs. 2 aBV zuwiderlaufende geschlechtsspezifische Unterscheidung bedeutet, war den Räten bewusst (Detailberatung der ständerätlichen Kommission vom 23. Oktober 1990; Beratung in der erweiterten Kommission für soziale Sicherheit des Nationalrates vom 23./24. November 1992). Der Gesetzgeber hat mit der unterschiedlichen Regelung der Voraussetzungen für Witwen- und Witwerrente somit explizit eine geschlechtsspezifische Unterscheidung vorgenommen, die sich weder wegen biologischer noch wegen funktionaler Verschiedenheiten aufdrängt. Der Bundesrat hat in seiner Botschaft zur (abgelehnten) 11. AHV-Revision (BBl 2000 1959 f.) klar darauf hingewiesen, die Regelung, wonach Witwer nur solange Anspruch auf Witwerrente haben, als das jüngste Kind unter 18 Jahre alt ist, widerspreche dem Grundsatz der Gleichbehandlung von Frau und Mann, weswegen die Leistungsberechtigung vereinheitlicht werden müsse. Der Bundesrat wollte - dem Gedanken des Versorgerschadens entsprechend - die Anspruchsvoraussetzungen für die Witwenrente an jene für die Witwerrente angleichen. Nach dem Scheitern der 11. AHV-Revision blieb es bis heute bei der dargestellten, für das Bundesgericht und die anderen rechtsanwendenden Behörden massgebenden (<ref-law>) Bestimmung.
4. Dem Verfahrensausgang entsprechend werden die Gerichtskosten dem Beschwerdeführer auferlegt (<ref-law>). Die unentgeltliche Rechtspflege (Prozessführung und Verbeiständung; <ref-law>) kann gewährt werden (<ref-ruling> E. 4a S. 202 und 371 E. 5b S. 372; Urteil 5P_458/2006 vom 6. Dezember 2006, E. 2.3). Es wird indessen auf <ref-law> aufmerksam gemacht, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten haben wird, wenn sie später dazu in der Lage ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt.
3. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4. Rechtsanwalt Andreas Fäh, St. Gallen, wird als unentgeltlicher Anwalt des Beschwerdeführers bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2'800.- ausgerichtet.
5. Dieses Urteil wird den Parteien, dem Obergericht Appenzell Ausserrhoden und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 4. Mai 2012
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Meyer
Die Gerichtsschreiberin: Bollinger Hammerle