Comencemos por el diccionario etimológico de Corominas. En este se propone:
TOCAYO, 1739. Origen incierto. Probablemente empezarían llamándose tocayo y tocaya las parejas que llevaban un mismo nombre, por alusión a la frase ritual del Derecho romano Ubi tu Cajus, ibi ego Caia (donde tú seas llamado Cayo, a mí me llamarán Caya), que la esposa dirigía al novio al llegar a su casa la comitiva nupcial; empleada esta alusión por estudiantes que trataban de iniciar un galanteo con chicas del mismo nombre, el pueblo, sin entender la alusión, se apropiaría el vocablo, con aplicación generalizada. Como la documentación más antigua procede de España, no es probable que venga del náhuatl, donde, por lo demás, no hay palabra exactamente comparable, pues tocaytl sólo significa 'nombre'.
Las etimologías del náhuatl se pueden encontrar en el Fichero general de la RAE. Por ejemplo, esta que referencia un texto de 1944 (anterior a Corominas):
TOCAYO, YA. m. y f. Amér. Respecto de una persona, 'otra que tiene su mismo nombre'. (En Ac. sin indicación de origen). Proviene del náhuatl tocayotl o tocaitl 'nombre, tocayo'.
También se encuentra otra de 1973 con la misma etimología. Pero al parecer esta etimología es antigua, puesto que en 1804 ya se afirmaba:
Así, por exemplo, las palabras tocayo, petate, xícara, cacao, chocolate y tomate provienen de las mexicanas tocatl, petatl, ssicali, cacahuatl, chocolatl y ssitomatl.
Otra ficha de 1942 profundiza en esta etimología, afirmado:
Así "nacatl", hace "nacaya", y "tocaitl", hace TOCAYO. Inemdiatamente pensamos, que si "nacayo" era la propia carne vista por Quetzalcóatl en el espejo, "tocayo" debe ser el propio nombre usado por otra persona. El empleo de la desinencia "yo", sería expresar igualdad objetiva con el sujeto significado en el vocablo al cual se agregaba. Esto podemos entenderlo mejor si consideramos que la partícula "yo", manifiesta una forma pronominal.
Argumenta la ficha que esa partícula "yo" actuaría a modo de pronombre reflexivo, por lo que de tocaitl 'nombre' se pasaría a tocayo 'mi nombre' o 'nuestro nombre'.
Acerca de sus primeros usos, no encuentro casos claros ni en el CORDE ni en la hemeroteca de la BNE antes de 1800. Sin embargo, Corominas data su primer uso en 1739. Precisamente el año en el que aparece registrada en el Diccionario de Autoridades:
TOCAYO, YA. adj. Lo mismo que Colombroño.
Sí, colombroño está registrado en el DLE como sinónimo de tocayo.
Pero curiosamente, hay un diccionario anterior que también la recoge: el Stevens de 1706, que registra tocáyo y la traduce al inglés como namesake, la cual suele ser su traducción más común y aproximada.
En todo caso, sus primeros registros no son demasiado antiguos, por lo que la posibilidad de que provenga del náhuatl no debería descartarse muy a la ligera. Y menos teniendo en cuenta que muchas fichas la recogen como un americanismo. Pero no se vayan todavía, que aún hay más. Leo en un par de fichas de 1894 la siguiente posibilidad:
Toca, tocayo = "colombroño" y también "camarada". En ambas acepciones se deriva del idioma quiché la voz toca ó tocayo: como sinónimo de colombroño se compone de estas dos raíces:
- to = "ayudar, auxiliar, servir", y
- ca ó cay = "dos".
Por tanto to+ca ó to+cay = "sirve á dos", es decir "nombre común a dos personas".
Así pues, ahora mismo la guerra parece que está entre los defensores de la etimología latina, como Corominas y también Moliner, y los defensores de la etimología del náhuatl, como se lee en el siguiente texto, que mucho antes del diccionario etimológico de Corominas ya calificaba su etimología como "fantástica":
Entre las etimologías más fantásticas está la de tocayo, referente a aquellas palabras matrimoniales en el derecho romano: Ubi tu Caius, ibi ego Caia; el libro a que nos referimos antepone naturalmente a esta fantasía los orígenes propuestos por Monlau y Vicuña Mackenna.
Marco Fidel Suárez, "Sueños de Luciano Pulgar, III", 1923 (Colombia).