Вот документик по Одессе (320 кил)
Из памятной книжки краснофлотца 1945 год
Как видим Одесса и Севастополь названы в тексте
городами-героями но с маленькой буквы.
Ленинград не назван.
Скорее всего до 1965 года данное словосочетание
использовалось как стандартный эпитет
(также как город-труженник или город-слодат)
и не обязательно, т.е. несло вторичный характер.
