El 14 de abril de 1942 nació en Medellín. Once días después murió Victoriano Rodríguez, su padre, y el recién nacido quedó a cargo de doña Gertrudis Gutiérrez, quien lo crió y lo sacó adelante.
Su infancia no fue fácil. Vendió limones en la Plaza de Cisneros, repartió carbón en las casas y voceó periódicos en las esquinas y calles de su ciudad. También trabajó como mensajero de una droguería, un muy buen ejercicio para cualquier aprendiz de ciclista pues endureció sus piernas subiendo a diario con una bicicleta que parecía de plomo por la empinada calle Ecuador con destino al barrio Manrique. Su apodo se lo ganó en las esquinas de ese barrio. Fue de tanto que les hablaba a sus amigos de la película La flecha rota, en la que el actor Jeff Chandler, el protagonista, representaba a un jefe indio llamado Cochise. Dicho sea de paso, en Arizona, Estados Unidos, una población lleva este nombre.
En febrero de 1958, cuando tenía 15 años, compitió por primera vez. Fue una doble a Girardota, un municipio cercano a Medellín, prueba que reunió a 150 turismeros. "A propósito, era una cicla de mujer. Paramos media hora en Girardota para tomar gaseosa y nos regresamos, pero tuve que abandonar por calambres", recuerda.
Era una época en la que no existía una preparación científica y los colombianos no tenían casi ninguna posibilidad de competir en el exterior. Pero Cochise tuvo la suerte de tener como compañero de equipo a Javier el 'Ñato' Suárez, el mejor escalador de su época, quien logró llevar a Cochise a la excelencia.
Tres años después, en 1961, comenzó a escribir su gran historia. Acababa de cumplir 19 años y participó en el primer Clásico RCN. En esta prueba se proclamó como la gran revelación del ciclismo colombiano al clasificarse segundo, detrás del 'Tigrillo de Pereira' Rubén Darío Gómez. Ese mismo año Cochise ganó su primera etapa en una Vuelta a Colombia. Fue el 29 de mayo de 1961 entre Armenia-Tuluá, Los narradores creyeron que el vencedor había sido Hernán Medina (campeón de la Vuelta de 1960) y sólo unos 20 minutos después se dieron cuenta que el ganador era un novato apodado Cochise, un nombre que a partir de entonces resonaría por todos los rincones del país. Al terminar la prueba se clasificó sexto y ganó el título de campeón novato.
En 1962 protagonizó una de las vueltas más cerradas de la historia. En una época en la que lo normal era de que el campeón de la vuelta lo hiciera con decenas de minutos y hasta horas de ventaja sobre el segundo, Cochise perdió el título ante el boyacense Roberto 'Pajarito' Buitrago (el primer campeón de esa tierra de grandes ciclistas) por apenas ocho segundos.
Pero en 1963 la victoria no se le escapó. Y tampoco en 1964, cuando se impuso con una hora y cuatro minutos de ventaja sobre Rubén Darío Gómez, además de obtener los títulos de la montaña y el de metas volantes.
En 1965 perdió la vuelta en la última etapa con el 'Ñato' Suárez. Aún hoy Cochise sospecha que le dieron de beber de una caramañola en la que introdujeron alguna sustancia extraña. "Yo era tan confiado y tan fuerte el calor en La Dorada que recibía todo lo que me pasaran". En 1966 y 1967 volvió a consagrarse campeón de la vuelta y fue subcampeón en 1969. Una hepatitis que sufrió en aquel año dio como resultado su pobre actuación en la vuelta de 1970, que ganó el novato Rafael Antonio Niño, de Cucaita, Boyacá, a quien proclamaron como su sucesor.
En los años 70 Cochise no volvió a destacarse en las rutas colombianas. Las etapas de montaña se habían vuelto una verdadera pesadilla para él. Parecía el fin. Pero gracias al preparador italiano Claudio Costa, Cochise renació, ya no como un monstruo de las carreteras sino de la pista. Y valió la pena. Aunque en los campeonatos mundiales de 1970, celebrados en Leicester, Gran Bretaña, a duras penas se clasificó quinto en la persecución individual, el 7 de octubre, en el velódromo de Ciudad de México, batió el récord mundial de la hora para aficionados al recorrer 47 kilómetros y 566 metros, 52,55 metros más que el danés Mogens Frey, quien había impuesto su marca un año atrás. "Pocos creían en mis condiciones, pero eso ya no importa. Este es mi más grande triunfo y estoy muy emocionado. Se lo dedico a toda Colombia y a México, porque ésta también es tierra nuestra", dijo al bajar de su bicicleta.
Al comenzar 1971 Cochise estaba en su mejor forma. Ganó su tercera vuelta al Táchira, ganó dos medallas de oro en los Juegos Panamericanos de Cali, en 4.000 metros persecución individual y por equipos, y el viernes 27 de agosto de 1971 conquistó su segundo título mundial al ganar la medalla de oro en los 4.000 metros persecución individual de los mundiales en Varese, Italia, superando al suizo Joseph Fuchs.
Esta carrera se transmitió por televisión y el comentarista Julio Arrastía, quien estaba confundido, le hizo creer al país que el suizo iba ganando con gran facilidad. "Mala cosa, no me gusta esto. Apenas faltan tres vueltas y Cochise pierde más de cuatro segundos", exclamó Arrastía. Por suerte era un error ('casi nos matás de un infarto, Julio', tituló al día siguiente el diario El Colombiano, de Medellín) y Colombia festejó como pocas veces lo había hecho gracias a Martín Emilio Cochise Rodríguez.
Su registro de 4 minutos, 53 segundos y 78 centésimas fue el mejor de toda la temporada. "Llevo seis años en el ciclismo de alta categoría, pero esta fue la noche que siempre había esperado. Me siento más que feliz", dijo. Dos días más tarde Cochise fue recibido en Bogotá con un entusiasmo que pocas veces se había visto.
Tras esta victoria se pensaba que muy probablemente Cochise podría conquistar la medalla de oro en los Juegos Olímpicos de Munich. Sin embargo el Comité Olímpico Internacional, que en aquel entonces dirigía un aristócrata de Chicago llamado Avery Brundage, estaba empeñado en buscar chivos expiatorios en una muy poco transparente cruzada en favor del amateurismo. A Cochise se le acusó de ser profesional porque había recibido un automóvil Ford como premio al ganar su tercera vuelta al Táchira, por aparecer en un aviso institucional de Proexpo y porque en México, mientras se preparaba para batir el récord de la hora, había entrenado con una camiseta de Benotto, casa italiana fabricante de bicicletas.
El periodista barranquillero Edgar A. Senior se encargó de hacerle el trabajo sucio al COI, que veía con muy buenos ojos que los deportistas del bloque soviético recibieran toda clase de apoyo económico de sus países y que a los atletas de Estados Unidos los sostuvieran a través de las universidades para prepararse, pero no podía tolerar que los deportistas del Tercer Mundo recibieran muy de vez en cuando algún incentivo para poder practicar su deporte sin tener que morirse de hambre. Gracias a Senior el Comité Olímpico Internacional declaró el 26 de mayo de 1972 que Cochise había violado el artículo 26 del reglamento olímpico.
Entonces se enroló en el equipo profesional italiano de la Bianchi Campagnolo, en el cual fue coequipero de Felice Gimondi. Ganó dos etapas en el Giro de Italia, corrió un Tour de Francia y junto con Gimondi obtuvo el trofeo Baracchi. Al retirarse del profesionalismo regresó a Medellín y compitió hasta 1982.