Sachverhalt: A. X._ (Ehemann) und Y._, nunmehr Z._, (Ehefrau) heirateten am xxxx 1996 in A._. Sie sind schweizerische und kambodschanische Staatsangehörige. Sie haben die gemeinsamen Kinder S._, geb. xxxx 1996, und T._, geb. xxxx 2000. B. Nachdem mit Eingabe vom 7. Juli 2003 die Parteien gemeinsam die Scheidung ihrer Ehe verlangt und ihren Scheidungswillen nach der Bedenkfrist schriftlich bestätigt hatten, reichte die Ehefrau am 4. Februar 2004 die Scheidungsklage ein, in welcher sie u.a. das Sorgerecht über die Kinder und Unterhalt von Fr. 550.-- pro Kind verlangte. Mit Urteil vom 8. April 2010 schied das Bezirksgericht Lenzburg die Ehe. Es teilte die Kinder der Ehefrau zu, unter Verzicht auf eine Besuchsregelung, und verpflichtete den Ehemann zu Kinderalimenten von je Fr. 330.--, zzgl. allfälligen Kinderzulagen (ausgehend von einem Einkommen der Ehefrau von Fr. 4'500.-- und des Ehemannes von Fr. 3'000.--). Sodann regelte es das Güterrecht und die weiteren Scheidungsnebenfolgen. Auf Appellation und Anschlussappellation hin erhöhte das Obergericht des Kantons Aargau mit Urteil vom 23. Dezember 2010 die Kinderalimente auf je Fr. 500.-- (zzgl. allfälliger Kinderzulagen) und setzte die güterrechtliche Leistung an den Ehemann auf Fr. 69'643.20 fest; im Übrigen wies es Appellation und Anschlussappellation ab. Hiergegen reichte der Ehemann eine Beschwerde in Zivilsachen ein. Mit Urteil vom 9. Juni 2011 hob das Bundesgericht das obergerichtliche Urteil mit Bezug auf den Kinderunterhalt auf und wies die Sache diesbezüglich zur Feststellung des rechtserheblichen Sachverhaltes und zur neuen Entscheidung an das Obergericht zurück; im Übrigen wies es die Beschwerde ab, soweit es darauf eintrat. Mit Urteil vom 23. Mai 2012 stellte das Obergericht fest, dass der Ehemann seinen beiden Kindern bis zum 23. Mai 2014 keinen Unterhalt schuldet, aber es verpflichtete ihn zu Unterhaltsbeiträgen von Fr. 500.-- (zzgl. allfälligen Kinderzulagen) pro Kind ab 24. Mai 2014 bis zur jeweiligen Mündigkeit der Kinder (ausgehend von einem sofortigen hypothetischen Einkommen des Ehemannes von Fr. 3'500.-- und einem hypothetischen Einkommen seiner neuen Ehefrau ab 24. Mai 2014). Die obergerichtlichen Verfahrenskosten auferlegte es der Ehefrau zu einem und dem Ehemann zu drei Vierteln; sodann verpflichtete es den Ehemann zur Hälfte der Anwaltskosten der Ehefrau für das obergerichtliche Verfahren. C. Gegen dieses Urteil hat X._ wiederum eine Beschwerde in Zivilsachen bzw. eventualiter eine subsidiäre Verfassungsbeschwerde erhoben mit dem Begehren um Feststellung, dass er (ausgehend von einem Einkommen von Fr. 200.--) seinen beiden Kindern keinen Unterhalt schulde. Sodann verlangt er die hälftige Verlegung der obergerichtlichen Gerichtskosten und die Wettschlagung der betreffenden Parteikosten, eventualiter eine Rückweisung an die Vorinstanz zur Neubeurteilung im Kostenpunkt. Ferner stellt er ein Gesuch um unentgeltliche Rechtspflege. Mit Schreiben vom 6. August 2012 hat das Obergericht auf eine Vernehmlassung verzichtet. Die Beschwerdegegnerin hat mit Vernehmlassung vom 20. September 2012 die Begehren gestellt, die Beschwerde in Zivilsachen bzw. subsidiäre Verfassungsbeschwerde sei abzuweisen, soweit darauf einzutreten sei. Die Beschwerdegegnerin verlangt ebenfalls die unentgeltliche Rechtspflege.