Sachverhalt:
A. Z._ und X._ heirateten am xxxx 1996. Sie haben die gemeinsamen Kinder R._, geb. xxxx 1997, S._, geb. xxxx 1998, und T._, geb. xxxx 2000.
Mit Urteil vom 17. August 2004 schied das Bezirksgericht Zürich die Ehe zwischen Z._ und X._. Es stellte die drei Kinder unter die elterliche Sorge der Mutter und genehmigte im Übrigen die Scheidungskonvention, welche u.a. Unterhaltsbeiträge von Fr. 560.-- pro Kind vorsah. Auf nachehelichen Unterhalt wurde zufolge mangelnder Leistungsfähigkeit des Ehemannes verzichtet.
X._ hat am xxxx 2009 wieder geheiratet und mit seiner neuen Ehefrau Y._ die gemeinsame Tochter W._, geb. xxxx 2010. Sie erwarten wiederum Nachwuchs.
B. Mit Klage vom 8. Dezember 2009 verlangte X._ die Abänderung des im Scheidungsurteil festgelegten Kinderunterhaltes.
Mit Urteil vom 14. Juni 2010 setzte das Kantonsgericht Appenzell Ausserrhoden die Unterhaltsbeiträge mit Wirkung ab Februar 2010 auf Fr. 400.-- pro Kind fest.
Das Obergericht ging in seinem Urteil vom 25. Oktober 2011 ebenfalls von veränderten Verhältnissen aus und setzte die Unterhaltsbeiträge für Februar bis Dezember 2010 auf Fr. 550.-- sowie ab Januar 2011 auf Fr. 543.-- pro Kind fest.
C. Gegen das obergerichtliche Urteil hat X._ eine Beschwerde in Zivilsachen erhoben mit dem Begehren um dessen Aufhebung und Rückweisung der Angelegenheit zur Neubeurteilung an die Vorinstanz. Ausserdem verlangt er die unentgeltliche Rechtspflege. Es wurden keine Vernehmlassungen eingeholt.

Erwägungen:
1. Angefochten ist ein kantonal letztinstanzlicher Endentscheid in Zivilsachen (Art. 72 Abs. 1, Art. 75 Abs. 2 und Art. 90 BGG). Der Mindeststreitwert von Fr. 30'000.-- gemäss <ref-law> dürfte vor dem Hintergrund der auf <ref-law> gestützten Kapitalisierung erreicht sein, da es dem Beschwerdeführer um eine substanzielle Reduktion der Kinderunterhaltsbeiträge.
Dieses materielle Anliegen, wie es aus der Beschwerdebegründung hervorgeht, entbindet den Beschwerdeführer indes nicht davon, ein Rechtsbegehren in der Sache selbst zu stellen: Die Beschwerde in Zivilsachen ist ein reformatorisches Rechtsmittel (<ref-law>). Daher darf sich der Beschwerdeführer mit Ausnahme des Falles, dass das Bundesgericht bei Gutheissung der Beschwerde nicht selbst entscheiden könnte, weil die erforderlichen Sachverhaltsfeststellungen der Vorinstanz fehlen, nicht darauf beschränken, die Aufhebung des angefochtenen Entscheides zu beantragen (<ref-ruling> E. 3.1 S. 490; <ref-ruling> E. 1.3 S. 383; <ref-ruling> E. 1.2 S. 135). Soweit es um Geldforderungen geht, ist der Antrag überdies zu beziffern (<ref-ruling> E. 2 S. 236 f.), jedenfalls soweit sich nicht aus der Begründung ohne weiteres ergibt, auf welchen Betrag der Rechtssuchende eine Geldleistung festgesetzt wissen will (<ref-ruling> E. 1b S. 414). Ein Begehren um "Festlegung des Geschuldeten" oder "angemessene Reduktion" bzw. "angemessene Erhöhung" wäre unstatthaft (<ref-ruling> E. 1 S. 392). Dies gilt ebenfalls im Zusammenhang mit Unterhaltsbegehren; deshalb sind insbesondere auch Anträge auf Festlegung der üblichen, angemessenen oder gesetzlichen Leistungen ungenügend (BGE 79 II 253 E. 1 S. 255; Urteile 5A_256/2007 vom 20. Juli 2007 E. 1; 5A_669/2007 vom 4. August 2008 E. 1.2.1). Diese Grundsätze gelten ausdrücklich auch dort, wo im Zusammenhang mit Unterhaltsforderungen für Kinder die Offizialmaxime und der Untersuchungsgrundsatz zum Tragen kommen (<ref-ruling> E. 4.5 bzw. E. 5 S. 620 f.).
Vorliegend beschränkt sich der Beschwerdeführer auf einen Rückweisungsantrag, obwohl im angefochtenen Urteil sämtliche notwendigen Sachverhaltselemente (alle relevanten Einkommens- und Bedarfszahlen des Scheidungsurteils; aktuelle Einkommen und Bedarfszahlen beider Parteien) festgestellt sind. Sodann lässt sich auch der Beschwerdebegründung nicht entnehmen, welche Unterhaltsbeträge der Beschwerdeführer festgesetzt haben möchte. Auf die Beschwerde in Zivilsachen kann deshalb nicht eingetreten werden.
2. Nur der Vollständigkeit halber sei festgehalten, dass der Beschwerde ohnehin auch in der Sache selbst kein Erfolg beschieden sein könnte:
Der Beschwerdeführer anerkennt für das vorliegende Beschwerdeverfahren ausdrücklich die für ihn vorgenommene Bedarfsberechnung (Beschwerde Ziff. IV.6). Er ficht einzig an, dass das Obergericht das Einkommen der Mutter nicht in eine Gesamtrechnung einbezogen hat mit der Begründung, angesichts der Erziehungspflichten für die drei Kinder leiste sie mit einem 80%-Pensum mehr, als sie eigentlich müsste. Der Beschwerdeführer macht geltend, dies könne nur für ein hypothetisches, nicht aber für ein tatsächliches Einkommen gelten; die vorinstanzliche Betrachtungsweise sei auch insofern stossend, als seine neue Familie unter dem Existenzminimum lebe, während sich bei der Beschwerdegegnerin ein Überschuss ergebe.
Diesem Vorbringen kann nicht gefolgt werden. Die Beschwerdegegnerin, die im Scheidungszeitpunkt keiner Erwerbstätigkeit nachging, hat - offensichtlich gezwungen durch die ökonomischen Verhältnisse (kein nachehelicher Unterhalt; Kinderunterhaltsbeiträge, welche die effektiven Kinderkosten nicht decken) - sukzessive verschiedene Tätigkeiten aufgenommen und arbeitet nunmehr als Malerin mit einem Pensum von 80%. Dabei verdient sie netto Fr. 4'149.15 inkl. Kinderzulagen (angefochtener Entscheid S. 8). Gemäss § 4 Abs. 1 des zürcherischen Einführungsgesetzes zum Bundesgesetz über die Familienzulagen (EG FamZG) betragen die Kinderzulagen bis zum 12. Altersjahr Fr. 200.-- und danach Fr. 250.--. Das heisst, dass der effektive Nettolohn der Mutter unter Fr. 3'500.-- liegt. Davon muss sie nicht nur ihren eigenen Unterhalt bestreiten, sondern auch die Differenz zwischen den Kinderunterhaltsbeiträgen und den effektiv viel höheren Kinderkosten, wie sie sich im Raum Zürich gerichtsnotorisch ergeben (vgl. Zürcher Tabellen, welche bei drei und mehr Kindern von einem durchschnittlichen Totalbedarf pro Kind von Fr. 1'515.-- bis zum 12. Altersjahr und danach von Fr. 1'675.-- ausgehen).
Vor diesem Hintergrund hält die Erwägung des Obergerichts, das Einkommen der Mutter sei nicht in eine Gesamtrechnung einzubeziehen, sondern sie dürfe dieses vorweg für sich und die Kinder verwenden, vor Bundesrecht stand, zumal dem kantonalen Sachgericht bei der Unterhaltsfestsetzung und den anwendbaren Kriterien ein grosser Ermessensspielraum zukommt (<ref-ruling> E. 3a S. 141; <ref-ruling> E. 4 S. 580).
3. Bei Nichteintreten werden der beschwerdeführenden Partei praxisgemäss reduzierte Gerichtsgebühren auferlegt. Der Gegenpartei ist kein entschädigungspflichtiger Aufwand entstanden.
Wie die vorstehenden Erwägungen zeigen, ist die Beschwerde als von Anfang an aussichtslos zu betrachten, weshalb es an den materiellen Voraussetzungen der unentgeltlichen Rechtspflege fehlt (<ref-law>) und das entsprechende Gesuch deshalb abgewiesen werden muss.

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde in Zivilsachen wird nicht eingetreten.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht von Appenzell Ausserrhoden, 2. Abteilung, schriftlich mitgeteilt.
Lausanne, 10. Mai 2012
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Möckli