Born in Uriah, Alabama, Madison attended Escambia County High School, graduating in 1949.
He enrolled at Texas Tech University on an athletic scholarship, but left after his freshman year to join the United States Army.
He returned to Texas Tech in 1952, starting four games in the 1952 college football season before an injury cut short his career.
The 1988 Eagle team was named as mythical national champions by USA Today, and Madison earned the title of the High School Coach of the Year.
JA was coming off a 0–10 season, and in Madison's first year with the program he led them to a 10–3 record which included a state title.