Pues nos vamos a tener que remontar a muy antiguo. He encontrado una entrada en el diccionario español-italiano de Franciosini de 1620 que dice:
uallenate. [ che è nato in Madrid. di Madrid.
Las primeras ediciones del DLE no recogen esta acepción, pero sí lo hace el diccionario de Terreros y Pando de 1786, que dice:
BALLENATO. A los hijos de Madrid les dan por chasco el mismo nombre.
Viendo que la forma de escribir la palabra varía según el diccionario, relajo un poco el criterio de búsqueda y encuentro lo siguiente:
Siendo, pues, esto así, que uno solo no puede afrentar a reino, provincia, ciudad, república, ni pueblo entero, queda en limpio que no hay para qué salir a la venganza del reto de la tal afrenta, pues no lo es; porque ¡bueno sería que se matasen a cada paso los del pueblo de la Reloja con quien se lo llama, ni los cazoleros, berenjeneros, ballenatos, jaboneros, ni los de otros nombres y apellidos que andan por ahí en boca de los muchachos y de gente de poco más a menos!
Miguel de Cervantes Saavedra, "Segunda parte del ingenioso caballero don Quijote de la Mancha", 1615 (España).
Además de usar el término ballenato para referirse a los de Madrid, al parecer cazolero era como llamaban a los de Valladolid en tiempos de Felipe III (por su afición a comer cazuelas), según una ficha del Fichero general. Los berenjeneros eran los de Toledo (por su afición a las berenjenas) y jaboneros los de Getafe, Yepez y Ocaña, por el jabón que fabricaban.
En otra ficha encuentro más referencias:
—¿No bailaréis un poquito
al hoyo, como en Madrid?
—Sí, en buena fe. —Pues salid [...]
—¡Bien lo ha hecho el ballenato!
1595-98 Lope Vega - Galán escarm.
No es la única obra de Lope de Vega en la que aparece el término. Al parecer este escritor lo usaba bastante. En una nota a pie de página aclara que el término ballenato se usa para los hijos de Madrid o de la Ballena. ¿Hará referencia esto a algún barrio o calle de Madrid? Puede que no, porque en otra ficha leo que para el apodo "tomaron pie de un cuentecillo".
Y por fin en otra ficha encuentro la historia que ha mencionado ukemi en su respuesta... pero para apodar a los de Covides de Mena (en el valle de Mena, en Burgos). Se cuenta que "los vecinos de este pueblo, en la antigüedad, eran muy temidos y considerados por muy torpes y poco inteligentes. Ejemplo de ello es, dice, la anécdota del pellejo que es tomado por ballena". ¿Una misma historia que corrió de pueblo en pueblo? En otra ficha se lee:
Ballen·ato. [apodo de los madrileños ó hijos de la ballena, desde que salieron con brío armados de todas armas á detener junto al puente á una ballena que bajaba en una avenida por el Manzanares, y que luego resultó ser una albarda.
Esta nota se encuentra en el libro La lengua de Cervantes: gramática y diccionario de la lengua castellana en El ingenioso hidalgo don Quijote de la Mancha, de Julio Cejador y Frauca, escrito entre 1905 y 1906.
Sobre otros posibles apodos, no encuentro más que los mencionados gato y ballenato. Y la diferencia entre ambos apodos a día de hoy yo diría que es práctica: el apodo gato se puede entender dado que es más actual, mientras que ballenato está completamente en desuso y no te va a entender nadie (salvo los que conozcan la historia).
