An early version concerns the Spanish conflict with the Moors. Francisco Rodriguez Marí included a version in his monumental "Cantos populares españoles" of 1883:

De la patillas de un moro
tengo que hacer una escoba,
para que barra el quartel
la infantería española.

Del pellejo del rey moro
tengo que hacer un sofí,
paraa que se siente en él
el Capitán General

De las costillas de un moro
me atrevo a formar un puente,
para que pase la España
y su ejército valiente

The cockroach first appeared in a verse by José Joaquín Fernández de Lizardi, 1818, in his book "La Quijotita y su prima."
Un capitán de marina
que vino en una fragata
entre varios sonesitos
trajo el de "La Cucaracha."

Other verses are included in the article (also linked above), "Crónicas de una cucaracha," Carlos Vidales, Literatura Colombiana.
http://members.tripod.com/~Vidales/CUCARA02.HTM