Sachverhalt:
A. Der aus Mazedonien stammende X._ (geb. 1976) reiste 1990 im Rahmen des Familiennachzugs zu seinen Eltern in die Schweiz ein und erhielt die Niederlassungsbewilligung. Eine berufliche Ausbildung absolvierte er nicht. Am 3. August 1995 heiratete er in der Heimat die ebenfalls in Mazedonien geborene Y._, die in der Folge ebenfalls in die Schweiz einreiste und seither eine stets verlängerte Aufenthaltsbewilligung besitzt. Das Paar hat drei gemeinsame Kinder (die Tochter A._ [geb. 1997] sowie die beiden Söhne B._ [geb. 2003] und C._ [geb. 2004]). Gegen die Eheleute bestanden per 29. November 2011 Betreibungen und Verlustscheine von knapp Fr. 130'000.--. Die Ausstände bei der Sozialhilfe betrugen per 21. Oktober 2008 Fr. 82'148.65. Davon waren am 20. November 2007 Fr. 79'959.60 erlassen worden. X._ arbeitete seit 1991 in diversen Branchen als Hilfsarbeiter; er war wiederholt stellenlos oder als Temporär-Angestellter beschäftigt. Am 20. März 2012 schloss er mit der K._ GmbH einen Arbeitsvertrag als Maschinist ab.
B. X._ wurde in der Schweiz wie folgt strafrechtlich verurteilt:
- am 24. Februar 1999 vom Bezirksamt Zofingen wegen Widerhandlungen gegen das Strassenverkehrsgesetz zu einer bedingten Gefängnisstrafe von zehn Tagen und zu einer Busse von Fr. 600.--.
- am 6. Februar 2001 vom Untersuchungsrichteramt Gossau wegen mehrfacher Veruntreuung zu einer bedingten Gefängnisstrafe von sechs Wochen.
In der Folge verwarnte ihn das Migrationsamt des Kantons Thurgau mit Verfügung vom 7. März 2001 ausländerrechtlich ein erstes Mal.
X._ delinquierte weiter und wurde wie folgt verurteilt:
- am 24. Januar 2002 von der Bezirksgerichtskommission Steckborn wegen unrechtmässiger Aneignung und betrügerischem Missbrauch einer Datenverarbeitungsanlage zu einer unbedingten Freiheitsstrafe von zwei Monaten.
X._ hatte sich zuvor aus einem ihm überlassenen Personenwagen eine EC-Karte samt Code angeeignet und damit an einem Geldautomaten Fr. 900.-- abgehoben. Das Geld bezahlte er dem Geschädigten im Anschluss an die untersuchungsrichterliche Befragung zurück.
Mit Verfügung vom 18. Juli 2002 verwarnte ihn das Migrationsamt des Kantons Thurgau ausländerrechtlich das zweite Mal und drohte im die - altrechtliche - Ausweisung an.
Gegen X._ kamen folgende weitere Verurteilungen hinzu:
- am 30. Juni 2003 von der Bezirksanwaltschaft Winterthur wegen grober Verletzung der Verkehrsregeln zu einer unbedingten Gefängnisstrafe von 30 Tagen
- am 5. Oktober 2010 vom Bezirksgericht Bülach wegen mehrfacher sexueller Handlungen mit Kindern zu einer bedingten Geldstrafe von 180 Tagessätzen zu Fr. 30.-- und zu einer Busse von Fr. 1'000.--.
C. Nach Gewährung des rechtlichen Gehörs widerrief das Migrationsamt mit Verfügung vom 8. Juni 2011 die Niederlassungsbewilligungen von X._ und seinen Kindern sowie die Aufenthaltsbewilligung der Ehefrau und wies die Familie per 30. September 2011 aus der Schweiz weg. Den hiegegen erhobenen Rekurs wies das Departement für Justiz und Sicherheit des Kantons Thurgau mit Entscheid vom 24. Oktober 2011 ab.
Mit Urteil vom 4. April 2012 hiess das Verwaltungsgericht des Kantons Thurgau die gegen diesen Entscheid gerichtete Beschwerde von Ehefrau und Kindern gut. Es beliess der Ehefrau Y._ die Aufenthaltsbewilligung und den drei Kindern A._, B._ und C._ die Niederlassungsbewilligung. Die Beschwerde von X._ hingegen wies es ab (Ziff. 1 des Urteilsdispositives).
D. Mit Eingabe vom 18. Mai 2012 führt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, Ziff. 1 des letztgenannten Urteils und die diesem zugrunde liegende Verfügung des Migrationsamtes aufzuheben und vom Widerruf der Niederlassungsbewilligung abzusehen. Gleichzeitig wird um unentgeltliche Rechtspflege und Verbeiständung ersucht.
Das Migrationsamt beantragt, die Beschwerde abzuweisen. Das Verwaltungsgericht stellt denselben Antrag, ebenso das Bundesamt für Migration.
X._ hat sich mit Eingabe vom 21. September 2012 noch einmal geäussert.
E. Mit Verfügung vom 25. Mai 2012 hat der Abteilungspräsident der Beschwerde - antragsgemäss - aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Gegen kantonal letztinstanzliche Entscheide über den Widerruf der Niederlassungsbewilligung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig (Art. 82 lit. a, Art. 83 lit. c Ziff. 2 (e contrario) sowie <ref-law>; <ref-ruling> E. 1.2.1 S. 4), und der Beschwerdeführer ist zur Ergreifung dieses Rechtsmittels befugt (<ref-law>). Nicht eingetreten werden kann auf die Beschwerde hingegen, soweit damit die Aufhebung der Verfügung des Migrationsamtes vom 8. Juni 2011 verlangt wird. Diese ist durch das Urteil des Verwaltungsgerichts ersetzt worden (Devolutiveffekt) und gilt inhaltlich als mitangefochten (vgl. <ref-ruling> E. 1.4 S. 144).
1.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Es kann die Sachverhaltsfeststellung der Vorinstanz auf genügend begründete Rüge hin (<ref-law>) oder von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1, Art. 105 Abs. 1 und 2 BGG).
2. 2.1 Unter den Voraussetzungen von Art. 63 AuG kann die Niederlassungsbewilligung widerrufen werden. Einen Widerrufsgrund setzt ein Ausländer unter anderem dann, wenn er "zu einer längerfristigen Freiheitsstrafe verurteilt wurde" (Art. 62 lit. b AuG in Verbindung mit Art. 63 lit. a AuG). Als längerfristig im Sinne von Art. 62 lit. b AuG gilt eine Freiheitsstrafe, wenn ihre Dauer ein Jahr überschreitet (<ref-ruling> E. 4.2 und E. 4.5 S. 379 ff.).
Ebenso kann die Niederlassungsbewilligung widerrufen werden, wenn der Ausländer "in schwerwiegender Weise gegen die öffentliche Sicherheit und Ordnung in der Schweiz oder im Ausland verstossen hat oder diese gefährdet" (Art. 63 lit. b AuG). In solchen Fällen ist ein Bewilligungswiderruf - wie bei Art. 62 lit. b AuG (längerfristige Freiheitsstrafe) - sogar dann zulässig, wenn sich der Ausländer - wie vorliegend - seit mehr als 15 Jahren ununterbrochen und ordnungsgemäss in der Schweiz aufgehalten hat (Art. 63 Abs. 2 AuG).
2.2 Der Beschwerdeführer scheint zunächst aus einer selber zusammengestellten Kasuistik bundesgerichtlicher Urteile ableiten zu wollen, der Widerruf einer Niederlassungsbewilligung werde "überhaupt erst dann in Betracht gezogen (...), wenn die Strafdauer eine Zeit von mehr als zwei Jahren ausmacht oder sehr schwere Delikte gegen Leib und Leben bei fehlender Zurechnungsfähigkeit begangen worden sind".
Zwar hat, wer einen Widerrufsgrund gemäss Art. 63 lit. a in Verbindung mit Art. 62 Abs. 1 lit. b AuG (Verurteilung zu einer längerfristigen Freiheitsstrafe) gesetzt hat, zugleich auch in schwerwiegender Weise gegen die öffentliche Sicherheit und Ordnung im Sinne von Art. 63 Abs. 1 lit. b AuG verstossen (vgl. Urteil 2C_833/2011 vom 6. Juni 2012, E. 3.1). Wie das Bundesgericht aber im Urteil 2C_242/ 2011 vom 23. September 2011 (E. 3.3.1) entschieden hat, sind die Widerrufsgründe alternativ zu verstehen und reicht aus, dass einer davon erfüllt ist, damit die objektiven Voraussetzungen für den Widerruf der Niederlassungsbewilligung erfüllt sind:
"II découle de la systématique de l'art. 63 al. 1 LEtr que l'énumération des cas de révocation est alternative et qu'il suffit donc que l'un soit donné pour que la condition objective de révocation de l'autorisation soit remplie."
Die vom Beschwerdeführer zusammengetragene Kasuistik, verbunden mit der Argumentation, bei einer rechnerischen Gesamtdauer seiner Freiheitsstrafen von nicht einmal einem Jahr sei es schon "vom Grundsatz her ausgeschlossen (...), den Wideruf der Niederlassungsbewilligung (...) überhaupt erst in Erwägung zu ziehen", ist daher von vornherein nicht ausschlaggebend.
2.3 Anders als der Widerruf einer Aufenthaltsbewilligung (Art. 62 lit. c AuG), welcher voraussetzt, dass der Ausländer "erheblich oder wiederholt" gegen die öffentliche Sicherheit und Ordnung verstossen hat, bedingt ein Widerruf der Niederlassungsbewilligung i.S.v. Art. 63 Abs. 1 lit. b AuG, dass ein solcher Verstoss "in schwerwiegender Weise" erfolgt ist. Dass damit vergleichsweise erhöhte Anforderungen an den Widerruf der Niederlassungsbewilligung gestellt werden, erscheint überzeugend, vermittelt diese doch das gefestigtere Anwesenheitsrecht als eine blosse Aufenthaltsbewilligung und besteht bei niedergelassenen Ausländern oftmals eine vergleichsweise engere Verbindung zur Schweiz (vgl. <ref-ruling> E. 3.2 S. 303).
Der Widerrufsgrund von Art. 63 Abs. 1 lit. b AuG ist nach der Praxis erfüllt , wenn die ausländische Person durch ihr Handeln besonders hochwertige Rechtsgüter - wie namentlich die körperliche, psychische und sexuelle Integrität eines Menschen - verletzt oder in Gefahr gebracht hat, sich von strafrechtlichen Massnahmen nicht beeindrucken lässt und sich im Rahmen einer Gesamtbetrachtung zeigt, dass sie auch künftig weder gewillt noch fähig ist, sich an die Rechtsordnung zu halten (BGE 2C_828/2011 vom 12. Oktober 2012 E. 2.1, 137 II 297 E. 3 S. 302 ff.; Urteile 2C_562/2011 vom 21. November 2011 E. 3.2 und 2C_310/2011 vom 17. November 2011 E. 5). Dies bedeutet, dass auch eine Summierung von Verstössen, die für sich genommen für einen Widerruf nicht ausreichen würden, einen Bewilligungsentzug rechtfertigen können (vgl. Urteil 2C_310/2011 vom 17. November 2011 E. 5.1). Sogar das Bestehen von privatrechtlichen Schulden kann gegebenenfalls einen schwerwiegenden Verstoss gegen die öffentliche Ordnung darstellen, wenn die Verschuldung mutwillig erfolgt ist (vgl. ebenda).
2.4 Nach den für das Bundesgericht grundsätzlich verbindlichen Feststellungen der Vorinstanz ist der Beschwerdeführer seit 1999 wiederholt straffällig geworden, wobei er zunächst Verkehrs- und Vermögensdelikte beging. Mit Urteil vom 5. Oktober 2010 wurde er jedoch wegen mehrfacher sexueller Handlungen mit Kindern verurteilt. Gemäss diesem Urteil des Bezirksgerichts Bülach hat er am 23. September 2009 zwei Mal mit einer Minderjährigen (geb. 10. Januar 1995) Geschlechtsverkehr gehabt. Mit diesem Delikt verletzte er die sexuelle Integrität eines Kindes, was im Rahmen der Prüfung der Wiederrufsvoraussetzungen gemäss Art. 63 Abs. 1 lit. b AuG ganz besonders schwer wiegt. Zwar anerkannte das Bezirksgericht, dass der Beschwerdeführer irrtümlich annahm, das Kind sei im Zeitpunkt der Tatbegehung mindestens 16 Jahre alt gewesen, jedoch hätte er diesen Irrtum nach den Ausführungen im Strafurteil bei pflichtgemässer Vorsicht vermeiden können. Ferner fällt zu Ungunsten des Beschwerdeführers die Kumulation verschiedener zusätzlicher Aspekte ins Gewicht: Er wurde mehrfach strafrechtlich verurteilt, offensichtlich ohne dass die ausgesprochenen Strafen bei ihm einen nachhaltigen Eindruck hinterlassen hätten. Wohl würden diese einzelnen Verfehlungen ausserhalb des Bereiches der besonders hochwertigen Rechtsgüter je für sich allein nicht ausreichen, um die Niederlassungsbewilligung zu widerrufen. Zusammen mit dem Sexualdelikt und der nicht unerheblichen Schuldenwirtschaft ergibt sich aber im Rahmen der vorzunehmenden Gesamtbetrachtung, dass aufgrund der über viele Jahre hinweg entstandenen Summe der Verfehlungen davon ausgegangen werden muss, der Beschwerdeführer sei auch in Zukunft nicht fähig, sich an die geltende Rechtsordnung zu halten. Damit ist der Widerrufsgrund von Art. 63 Abs. 1 lit. b AuG erfüllt.
3. 3.1 Nach Art. 63 AuG "kann" die Niederlassungsbewilligung widerrufen werden. Die Massnahme muss - wie jedes staatliche Handeln - verhältnismässig sein (vgl. <ref-law>; Art. 96 AuG). Zur Beurteilung der Frage, ob dies der Fall ist, sind namentlich die Schwere des Delikts und des Verschuldens des Betroffenen, der seit der Tat vergangene Zeitraum, das Verhalten des Ausländers während diesem, der Grad seiner Integration bzw. die Dauer der bisherigen Anwesenheit sowie die ihm und seiner Familie drohenden Nachteile zu berücksichtigen (<ref-ruling> E. 4.3). Die Niederlassungsbewilligung eines Ausländers, der sich schon seit langer Zeit hier aufhält, soll zwar nur mit besonderer Zurückhaltung widerrufen werden, doch ist dies bei wiederholter bzw. schwerer Straffälligkeit selbst dann nicht ausgeschlossen, wenn er hier geboren ist und sein ganzes bisheriges Leben im Land verbracht hat (statt vieler BGE 2C_828/2011 vom 12. Oktober 2012 E. 2.2.1 mit zahlreichen Hinweisen).
3.2 Der Beschwerdeführer lebt zwar seit mehr als 20 Jahren in der Schweiz. Er ist aber nicht hier geboren und aufgewachsen und gilt damit nicht als so genannter "Ausländer der zweiten Generation". Nach den grundsätzlich verbindlichen Feststellungen der Vorinstanz war er sodann in den letzten Jahren während der meisten Zeit arbeitslos bzw. verlor allfällige Stellen nach kurzer Zeit wieder (angefochtener Entscheid S. 16); von einer erfolgreichen Integration kann - auch angesichts der nicht unerheblichen Schuldenwirtschaft - keine Rede sein. Dass er am 12. März 2012 einen neuen Arbeitsvertrag als Maschinist bekam, lässt heute (noch) keine andere Beurteilung zu. Besonders intensive private Beziehungen beruflicher oder gesellschaftlicher Natur, die ihm allenfalls einen Aufenthaltsanspruch gestützt auf Art. 8 EMRK (Schutz des Privatlebens) verschaffen könnten (vgl. <ref-ruling> E. 3.2.1 S. 286), sind jedenfalls nicht dargetan (<ref-law>).
3.3 Sein Verschulden wiegt sodann schwer: Das Sexualdelikt verstösst gegen das besonders hochwertige Rechtsgut der sexuellen Integrität eines Menschen (vorne E. 2.3). Sodann zeigen nicht nur das Sexualdelikt an einer Minderjährigen, sondern auch die Verkehrsregelverstösse und das dreiste Vermögensdelikt am Geldautomaten (vorne lit. B), dass der Beschwerdeführer sich nicht beherrscht und er sich nicht an die geltende Rechtsordnung halten kann. Auch zwei ausländerrechtliche Verwarnungen änderten daran nichts. Es sind im Gegenteil immer wieder neue Verfehlungen hinzugekommen, welche beim Beschwerdeführer die Wirkungslosigkeit der Androhung strengerer ausländerrechtlicher Massnahmen belegen. Sollen Verwarnungen im Sinne von Art. 96 Abs. 2 AuG aber Sinn machen, muss ihre Missachtung Folgen haben. Dies scheint der Beschwerdeführer nicht zu gewärtigen, weswegen vorliegend eine (dritte) blosse Androhung einer ausländerrechtlichen Massnahme - nämlich diejenige des Widerrufs der Niederlassungsbewilligung - ausser Frage steht.
3.4 Zwar fallen zu Gunsten des Beschwerdeführers die familiären Interessen ins Gewicht: Seine Familie mit den drei hier geborenen Kindern hat grosses Interesse, in der Schweiz bleiben zu können. Aufgrund des vorinstanzlichen Urteils haben aber sowohl die Ehefrau (Aufenthaltsbewilligung) wie auch die Kinder (Niederlassungsbewilligung) weiterhin ein Aufenthaltsrecht in der Schweiz. Nichts hindert die Kinder daran, hier aufzuwachsen und zur Schule zu gehen; die Betreuung durch mindestens einen Elternteil ist gewährleistet und der Kontakt zum Vater kann diesfalls durch gegenseitige Besuche oder mittels Briefvekehr, Telefonaten und den anderen Formen heutiger Informationstechnologie (E-Mail usw.) gepflegt werden. Sodann wäre eine freiwillige Ausreise von Frau und Kindern zusammen mit dem Beschwerdeführer möglich und steht im Ermessen der Familie. Die drei Kinder (heute 15, 9 und 8 Jahre alt) haben zwar nie in Mazedonien gelebt, stehen aber im Falle einer freiwilligen Ausreise in einer vergleichbaren Situation wie andere Kinder, die zusammen mit ihren Eltern in ein fremdes Land auswandern. Die Ehefrau schliesslich hat bis zu ihrer Heirat in Mazedonien gelebt, so dass eine Rückkehr dorthin für sie zumutbar erscheint, sollte sie sich für eine freiwillige Ausreise entscheiden. Die Garantie auf Schutz des Familienlebens (Art. 8 EMRK, <ref-law>) ist damit nicht verletzt, und der Widerruf der Niederlassungsbewilligung auch nicht unverhältnismässig.
4. Nach dem Gesagten erweist sich die Beschwerde als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
Der unterliegende Beschwerdeführer trägt grundsätzlich die Kosten des bundesgerichtlichen Verfahrens (<ref-law>). Da sich die Beschwerde aber nicht als aussichtslos erweist und der Beschwerdeführer bedürftig ist, kann seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung entsprochen und auf die Erhebung von Gerichtskosten verzichtet werden (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen:
2.1 Es werden keine Kosten erhoben.
2.2 Rechtsanwalt Robert P. Gehring, Frauenfeld, wird für das bundesgerichtliche Verfahren als unentgeltlicher Rechtsbeistand eingesetzt und aus der Gerichtskasse mit Fr. 2'000.-- entschädigt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Departement für Justiz und Sicherheit und dem Verwaltungsgericht des Kantons Thurgau sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 1. März 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Klopfenstein