Sachverhalt: A. B._ und A._, welche nie zusammengelebt haben, sind die Eltern der 2010 geborenen Tochter C._. Die Mutter war damals mit einem anderen Mann verheiratet und ist zwischenzeitlich eine neue Ehe eingegangen. Der Vater ist abgewiesener Asylant mit einem vorläufigen Bleiberecht und lebt von der Nothilfe in einer Notschlafstelle. Am Anfang hatte er noch Kontakt zu C._; seit Mai 2011 fand kein Kontakt mehr statt. B. Auf Gesuch des Vaters hin beschloss die Vormundschaftsbehörde U._ am 17. September 2012, dem Vater stehe gegenüber der Tochter im Oktober, November und Dezember 2012 ein begleitetes Besuchsrecht von jeweils zwei Stunden zu. Eine dagegen erhobene Beschwerde des Vaters wies das Departement für Justiz und Sicherheit am 12. Dezember 2012 ab. Am 19. Dezember 2012 ersuchte der Vater erneut um die Regelung des Besuchsrechts. Die KESB U._ räumte ihm mit Entscheid vom 24. April 2013 das Recht ein, seine Tochter jeden ersten und dritten Sonntag im Monat für jeweils zwei Stunden in Begleitung zu besuchen, unter Errichtung einer Besuchsbeistandschaft. Die Beiständin berichtete am 12. November 2013, dass die Mutter sich jeglicher Kooperation entziehe und sich das Besuchsrecht nicht durchsetzen lasse. Am 19. Februar 2014 genehmigte die KESB den Bericht, unter Aufrechterhaltung der Beistandschaft, und wies die Mutter unter Androhung einer Ungehorsamsstrafe nach Art. 292 StGB an, den persönlichen Verkehr zwischen Vater und Tochter zu ermöglichen. Am 16. Juli 2014 berichtete die Beiständin, der Vater suche nach wie vor den Kontakt zu seiner Tochter, aber die Mutter verweigere jegliche Kooperation; es sei ihr (Beiständin) unmöglich, ihre Aufgabe wahrzunehmen. C. Am 29. Juli 2014 beantragte der Vater, C._ sei unter die gemeinsame elterliche Sorge zu stellen und die angedrohte Ungehorsamsstrafe sei zu vollziehen. Die Mutter erklärte sich damit nicht einverstanden; der Vater könne keine Verantwortung tragen und sei im Umgang mit einem Kind überfordert. Am 19. Dezember 2014 ergänzte der Vater sein Gesuch dahingehend, dass die Beiständin ihn bei seinem ersten Schulbesuch begleiten und soweit erforderlich auch weitere Begleitungen im Schulbereich gewährleisten solle. Mit Entscheid vom 21./22. Januar 2015 genehmigte die KESB U._ den Bericht der Beiständin vom 16. Juli 2014 und hielt an der alleinigen elterlichen Sorge der Mutter fest. Ferner verfügte sie die Weiterführung der Beistandschaft und beauftragte die Beiständin mit der Organisation und Überwachung der seinerzeit angeordneten Besuche. Die hiergegen vom Vater erhobene Beschwerde wies das Obergericht des Kantons Thurgau mit Entscheid vom 11. März 2015 ab, soweit es darauf eintrat. D. Gegen den obergerichtlichen Entscheid hat der Vater eine Beschwerde in Zivilsachen erhoben mit dem Begehren, C._ sei unter die gemeinsame elterliche Sorge zu stellen; eventualiter verlangt er die Rückweisung der Sache an das Obergericht, unter Anweisung zur Errichtung einer Prozessbeistandschaft und Beigabe einer unentgeltlichen Kinderanwältin. Ferner verlangt er die unentgeltliche Rechtspflege. Mit Schreiben vom 17. Dezember 2015 hat das Obergericht die Abweisung der Beschwerde beantragt. Mit Vernehmlassung vom 20. Januar 2016 verlangt die Mutter die Abweisung der Beschwerde, soweit darauf einzutreten sei. Sodann verlangt auch sie die unentgeltliche Rechtspflege. Am 25. Februar 2016 wurde die Angelegenheit öffentlich beraten.