Иван Павлович Терещенко родился 30 января 1927 года в станице Новомихайловка Гулькевского района (ныне Отрадненский район) Краснодарского края. Мать – Полина. Отец – Павел Зиновеевич Терещенко. Образование получил неполное (3 класса) в связи с началом войны. Полгода жил на оккупированной немцами территории. В декабре 1944-го года был призван в ряды Советской Армии. Прошёл обучение в 120-й снайперской роте 105-го полка. В составе 6-го стрелкового батальона участвовал в военных операциях по ликвидации банд власовцев и бандеровцев. С 1947-го года в чине сержанта срочной службы служил в авиации мотористом, вначале в 56-м авиаполку, затем в 487-м авиаполку, базировавшихся в городе Городок Львовской области. За четыре года службы в 487-м авиаполку имел от командования 50 благодарностей, в том числе от маршала Советского Союза Вершинина. 24 августа 1950 года женился на Надежде Кирсановне Судаковой, вольнонаёмной служащей 52-го авиакорпуса.