Sachverhalt:
A. X._ wurde am 16. Januar 2002 verhaftet und am 30. Mai 2002 nach rund viereinhalb Monaten aus der Untersuchungshaft entlassen. Am 5. März 2003 fand die Schlusseinvernahme statt, anlässlich welcher ihm der Sachverhalt sowie die von der Bezirksanwaltschaft als erfüllt erachteten Gesetzesbestimmungen vorgehalten wurden (angefochtenes Urteil S. 5). Es wurde ihm als Folge dieses Verfahrens vom Migrationsamt die Aufenthaltsbewilligung für den Kanton Zürich entzogen, da er noch nicht drei Jahre im gemeinsamen Haushalt mit seiner Ehefrau gelebt hatte. Weil ihm auch der Kanton Aargau, wo seine Lebensgefährtin wohnte, eine Aufenthaltsbewilligung verweigerte, reiste er am 27. März 2003 in die USA aus und liess sich wieder - wie vor der Heirat - in Miami Beach nieder (obergerichtliches Urteil vom 23. Dezember 2004, S. 6).
Die Bezirksanwaltschaft des Kantons Zürich warf ihm mit Anklageschrift vom 29. Januar 2004 vor, er habe zwischen Oktober 2000 und Mai 2001 seine Nichte A._ mehrfach, das erste Mal vor ihrem 16. Geburtstag, zur Duldung sexueller Handlungen genötigt und sie einmal vergewaltigt. Weiter wurde ihm Sachbeschädigung zum Nachteil seiner damaligen Ehefrau angelastet.
B. Das Bezirksgericht Zürich verfügte mit Präsidialverfügung vom 13. Februar 2004, der Angeklagte habe persönlich (mit oder ohne Verteidiger oder Verteidigerin) zur Hauptverhandlung zu erscheinen.
An der Hauptverhandlung des Bezirksgerichts vom 27. April 2004 beantragte seine Verteidigerin B._, ihm das persönliche Erscheinen an der Verhandlung zu erlassen. "Aufgrund der glaubhaften Ausführungen der Verteidigung sowie des Umstands, dass der Angeklagte in der Untersuchung genügend Gelegenheit hatte, zu den gegen ihn erhobenen Vorwürfen Stellung zu nehmen, wurde dem Gesuch im Sinne von <ref-law>/ZH stattgegeben" (bezirksgerichtliches Urteil S. 3). Das Bezirksgericht bestrafte ihn wegen Vergewaltigung (<ref-law>), mehrfacher sexueller Nötigung (<ref-law>), sexueller Handlung mit einem Kind (<ref-law>) und Sachbeschädigung (<ref-law>) mit dreieinhalb Jahren Zuchthaus (wovon 134 Tage durch Untersuchungshaft erstanden waren) sowie mit sieben Jahren Landesverweisung. Er wurde verpflichtet, der Geschädigten eine Genugtuung von Fr. 18'000.-- zu bezahlen.
Die Verteidigerin erhob Berufung beim Obergericht des Kantons Zürich. Dieses bestätigte am 23. Dezember 2004 das bezirksgerichtliche Urteil vollumfänglich. Zum Verfahren hielt es fest: "Im Einverständnis mit den Parteien wurde das Berufungsverfahren schriftlich durchgeführt (Urkunden 57 - 60), nachdem dem Angeklagten schon vor erster Instanz das persönliche Erscheinen erlassen worden war" (Urteil S. 8).
Gegen das obergerichtliche Urteil erhob die Verteidigerin Nichtigkeitsbeschwerde beim Kassationsgericht des Kantons Zürich. Dieses wies die Beschwerde mit Sitzungsbeschluss vom 19. Dezember 2005 ab, soweit es darauf eintrat.
Das obergerichtliche Urteil und der kassationsgerichtliche Beschluss wurden nicht mit eidgenössischen Rechtsmitteln beim Bundesgericht angefochten. In Vollstreckung des obergerichtlichen Urteils wurde X._ am 5. Dezember 2006 auf Begehren der schweizerischen Behörden in Florida/USA festgenommen und am 3. Februar 2007 an die Schweiz ausgeliefert. Er befindet sich im Strafvollzug.
C. Rechtsanwalt C._ meldete mit Schreiben vom 3. Mai 2007 für X._ nachträgliche (erneute) kantonale Nichtigkeitsbeschwerde an. In der Folge reichte der heutige Rechtsvertreter die Beschwerdebegründung ein. X._ beantragte die Aufhebung des obergerichtlichen Urteils vom 23. Dezember 2004 und die Rückweisung der Sache an das Obergericht. Er machte im Wesentlichen geltend, er habe erst nach seiner Auslieferung an die Schweiz von der strafrechtlichen Verurteilung erfahren. Ferner konnte er sich vor Kassationsgericht zu den Stellungnahmen seiner früheren Verteidigerin (Akten des Kassationsgerichts, act. 62, 70 und 86), die er "im Umfang der in diesem Verfahren vor dem Kassationsgericht an [sie] gerichteten Vorwürfe vom Anwaltsgeheimnis entbunden hatte" (act. 61), äussern (act. 80 und 90). Beide Parteien verzichteten auf weitere Stellungnahmen.
Das Kassationsgericht des Kantons Zürich entliess zunächst mit Verfügung vom 6. Juli 2007 formell die frühere Verteidigerin als amtliche Verteidigerin (act. 36) und wies mit Verfügung vom 19. Juli 2007 die Gesuche von X._ um aufschiebende Wirkung und Entlassung aus dem ordentlichen Strafvollzug ab (act. 50). In der Folge trat es mit Zirkulationsbeschluss vom 3. April 2008 auf die nachträgliche Nichtigkeitsbeschwerde mit der Begründung nicht ein, wenn X._ heute geltend mache, er habe erst im Zusammenhang mit dem Auslieferungsverfahren von dem gegen ihn ergangenen Strafurteil erfahren, sei dies auf seine eigene Nachlässigkeit zurückzuführen. Es könne nicht gesagt werden, er habe seine Vorbringen ohne eigenes Verschulden nicht früher vortragen können.
D. X._ erhebt Beschwerde in Strafsachen und beantragt, den Beschluss des Kassationsgerichts vom 3. April 2008 aufzuheben und die Sache zur Durchführung des Verfahrens an dieses zurückzuweisen, eventuell den Beschluss sowie das Urteil des Obergerichts vom 23. Dezember 2004 aufzuheben und die Sache an das Obergericht zur Neubeurteilung zurückzuweisen. Er beantragt ferner die unentgeltliche Rechtspflege.
Das Kassationsgericht verzichtet auf Vernehmlassung. Die Oberstaatsanwaltschaft des Kantons Zürich beantragt unter Verweisung auf den angefochtenen Beschluss die Abweisung der Beschwerde.

Erwägungen:
1. Das Bundesgericht prüft die Verletzung von Grundrechten und von kantonalem Recht nur insofern, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-ruling> E. 3.2; <ref-ruling> E. 1.4). Dieses Rügeprinzip verlangt, dass in der Beschwerdeschrift dargelegt wird, welche verfassungsmässigen Rechte inwiefern durch den angefochtenen Entscheid verletzt worden sind. Das Bundesgericht prüft nur rechtsgenügend vorgebrachte, klar erhobene und, soweit möglich, belegte Rügen. Auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein (<ref-ruling> E. 3.1).
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), soweit nicht die Voraussetzungen von <ref-law> vorliegen (BGE <ref-ruling> E. 2.6). <ref-law> schliesst echte tatsächliche Noven im bundesgerichtlichen Beschwerdeverfahren aus (<ref-ruling>).
2. Der Beschwerdeführer macht geltend, er habe erst mit dem Auslieferungsverfahren von dem gegen ihn ergangenen Strafurteil erfahren. Mit dem Nichteintretensentscheid sei die Vorinstanz in überspitzten Formalismus verfallen und habe das Willkürverbot sowie den Grundsatz von Treu und Glauben verletzt und "im Ergebnis" zahlreiche weitere Rechtsverletzungen begangen (Beschwerde S. 8 f.).
2.1 Die Vorinstanz stellt fest, der Beschwerdeführer sei am 16. Januar 2002 verhaftet worden, nachdem die Geschädigte über eine Opferberatungsstelle der Polizei habe mitteilen lassen, sie wolle gegen ihn wegen sexueller Übergriffe Anzeige erstatten. Er sei am 30. Mai 2002 nach rund viereinhalbmonatiger Untersuchungshaft entlassen worden. An der Schlusseinvernahme vom 5. März 2003 sei ihm der Sachverhalt und die als erfüllt betrachteten Gesetzesbestimmungen vorgehalten worden. Ende März 2003 sei er nach Miami zurückgekehrt.
Der Beschwerdeführer habe somit gewusst, dass ein Strafverfahren gegen ihn laufe und dass es sich dabei nicht um eine Bagatelle handle. Soweit er geltend mache, die Verteidigerin habe ihn nicht informiert oder er habe diese telefonisch nicht erreichen können, sei ihm ohne weiteres zumutbar gewesen und hätte von ihm erwartet werden können, sich nach dem Verfahrensstand zu erkundigen. Auf jeden Fall habe er nicht über mehr als zwei Jahre hinweg mit einer solchen Erkundigung zuwarten und hoffen dürfen, das Verfahren sei wohl eingestellt worden. Die Behauptung des Beschwerdeführers, es hätten seitens der Verteidigerin keine Kontaktaufnahmen stattgefunden, erscheine angesichts der Stellungnahmen der Verteidigerin (oben E. C) unglaubhaft. Wenn er heute geltend mache, er habe erst im Zusammenhang mit dem Auslieferungsverfahren von dem gegen ihn ergangenen Strafurteil erfahren, sei dies auf seine eigene Nachlässigkeit zurückzuführen. Es könne nicht gesagt werden, er habe seine Vorbringen ohne eigenes Verschulden nicht früher vortragen können. Auf die nachträgliche Nichtigkeitsbeschwerde sei nicht einzutreten.
2.2 Beschwerdegegenstand bildet allein dieser vorinstanzliche Nichteintretensentscheid gemäss § 431 Satz 1 der Strafprozessordnung des Kantons Zürich (StPO/ZH). In diesem Zusammenhang rügt der Beschwerdeführer im Wesentlichen eine formelle Rechtsverweigerung. Auf das rechtskräftige Strafverfahren betreffende Verfahrensrügen und Vorbringen im Eventualstandpunkt ist nicht einzutreten.
2.2.1 Jede Person hat in Verfahren vor Gerichts- und Verwaltungsbehörden Anspruch auf gleiche und gerechte Behandlung, auf Beurteilung innert angemessener Frist (<ref-law>) und auf rechtliches Gehör (<ref-law>). Tritt eine Behörde auf eine ihr unterbreitete Sache nicht ein, obschon sie darüber entscheiden müsste, begeht sie eine formelle Rechtsverweigerung (<ref-ruling> E. 3a). Das aus <ref-law> fliessende Verbot des überspitzten Formalismus wendet sich gegen prozessuale Formstrenge, die als exzessiv erscheint, durch kein schutzwürdiges Interesse gerechtfertigt ist, zum blossen Selbstzweck wird und die Verwirklichung des materiellen Rechts in unhaltbarer Weise erschwert oder gar verhindert. Das Bundesgericht prüft frei, ob eine solche Rechtsverweigerung vorliegt (<ref-ruling> E. 2a; <ref-ruling> E. 5.4.1). Neben dieser Prüfung kommt jener gemäss <ref-law> keine weitergehende Bedeutung zu.
2.2.2 Gemäss <ref-law>/ZH ist die Nichtigkeitsbeschwerde an das Kassationsgericht binnen zehn Tagen, von der Eröffnung des Entscheids oder (subsidiär) der Entdeckung des Mangels an gerechnet, beim Präsidenten des urteilenden Gerichts anzumelden. Diese subsidiäre Frist soll den Parteien auch nachträglich die Geltendmachung von Nichtigkeitsgründen ermöglichen. Dabei spielt es keine Rolle, ob bereits innert ordentlicher Frist eine Nichtigkeitsbeschwerde angemeldet, begründet und behandelt worden ist. Nachträglich können nur Nichtigkeitsgründe geltend gemacht werden, welche die Partei ohne ihr Verschulden nicht schon vorher vorbringen konnte. Sie muss glaubhaft machen, dass sie zum vorherigen Anbringen nicht in der Lage gewesen ist. Ist das späte Feststellen eines angeblichen Mangels auf Nachlässigkeit zurückzuführen, wird auf die Nichtigkeitsbeschwerde nicht eingetreten (angefochtenes Urteil S. 4 f.).
Die nachträgliche Nichtigkeitsbeschwerde ist somit nur gegeben, wenn der Fehler nicht innert ordentlicher Frist erkennbar war, nicht aber etwa bei unsorgfältiger oder verspäteter Aktenanalyse oder wenn ein neu beigezogener Verteidiger einen anderen Standpunkt vertritt als der frühere (NIKLAUS SCHMID, Strafprozessrecht, 4. Auflage, Zürich 2004, S. 406 Fn. 326). Die Partei hat den Nachweis der rechtzeitigen Fristwahrung zu erbringen. Die Frist beginnt mit der Entdeckung des Mangels durch die Partei zu laufen, nicht erst durch einen nachträglich beigezogenen Verteidiger. Eine Fristversäumnis durch anwaltliches Verschulden würde allerdings bei notwendiger Verteidigung der Partei nicht zugerechnet (oben in E. C erwähnte vorinstanzliche Verfügung vom 19. Juli 2007, S. 7 und 9). Im Übrigen kann angemerkt werden, dass selbst mängelbehaftete Urteile in Rechtskraft erwachsen, wenn sie nicht fristgemäss und gesetzeskonform angefochten werden.
2.2.3 Sachverhaltlich ist davon auszugehen, dass der Beschwerdeführer nach der Schlusseinvernahme Ende März 2003 die Schweiz verliess. Am 29. Januar 2004 wurde Anklage erhoben. Er verzichtete ausdrücklich auf eine Anwesenheit vor Bezirks- und Obergericht. Mit dem abschliessenden kassationsgerichtlichen Urteil vom 19. Dezember 2005 wurde das Strafurteil vollstreckbar (oben E. A und B). Die Sache wurde somit durch drei Gerichtsinstanzen beurteilt. Dabei wurde der Beschwerdeführer während des gesamten Strafverfahrens von derselben Rechtsanwältin amtlich verteidigt. Diese vertrat ihn gleichzeitig im Ehescheidungsverfahren. Ihre Vertretungshandlungen muss sich der Beschwerdeführer anrechnen lassen. Dennoch behauptet dieser heute, im Rahmen des Auslieferungsverfahrens erstmals von der Verurteilung erfahren zu haben.
Abgesehen davon, dass die Verteidigung im gesamten Strafverfahren nie in Frage gestellt wurde und die Verteidigerin seiner Behauptung widerspricht, lässt sich angesichts des schwerwiegenden Vorhalts an der Schlusseinvernahme vom 5. März 2003 nicht annehmen, der Beschwerdeführer habe nicht mit einem Strafurteil gerechnet. Vielmehr war das Strafverfahren mit der Untersuchungshaft, den Untersuchungshandlungen und der Schlusseinvernahme augenscheinlich bereits im Gange. Auch der Laie weiss, dass dann in der Regel ein Strafurteil gefällt wird. Soweit der Beschwerdeführer einwendet, er habe gemeint, das Verfahren werde eingestellt, erwartete er zumindest ein solches Urteil. Mit der Eröffnung einer Strafuntersuchung entsteht denn auch ein Prozessrechtsverhältnis (vgl. <ref-ruling> E. 1.2.3; <ref-ruling>; <ref-ruling>). Würde seine Behauptung unterstellt, seine Verteidigerin habe ihn nicht informiert, hätte er sich bei dieser oder bei den ihm aus der Strafuntersuchung bekannten Behörden informieren können und müssen (auch seine in der Schweiz wohnhafte Lebensgefährtin hatte zuvor mehrmals die Verteidigerin kontaktiert). Dass er im Scheidungsverfahren mit den Zivilbehörden von sich aus am 14. Februar 2005 persönlich telefonischen Kontakt aufgenommen hatte (Beschwerde S. 35 f.), belegt, dass er zu einem solchen Vorgehen selber in der Lage und befähigt war. Er hätte sich auch im Strafverfahren Klarheit verschaffen können, wenn Klärungsbedarf bestanden haben sollte.
Von der bezirksgerichtlichen Hauptverhandlung bis zur Anmeldung der subsidiären Nichtigkeitsbeschwerde vergingen drei und seit der Schlusseinvernahme vier Jahre. Auf die Beschwerde ist aber nur einzutreten, wenn sie erstens binnen zehn Tagen seit der Entdeckung des Mangels angemeldet und zweitens glaubhaft gemacht wird, dass der behauptete Mangel ohne Verschulden nicht vorher hatte vorgebracht werden können (oben E. 2.2.2). Dies verneint die Vorinstanz. Die geltend gemachte Verfassungsverletzung ist nicht begründet.
3. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Das Gesuch um unentgeltliche Rechtspflege kann gutgeheissen werden. Entsprechend sind keine Kosten zu erheben. Der Rechtsvertreter des Beschwerdeführers ist aus der Bundesgerichtskasse zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird gutgeheissen.
3. Es werden keine Kosten erhoben.
4. Der Rechtsvertreter des Beschwerdeführers wird aus der Bundesgerichtskasse mit Fr. 3'000.-- entschädigt.
5. Dieses Urteil wird den Parteien und dem Kassationsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 28. November 2008
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Schneider Briw