Leben Schultz-Gerstein legte 1963 an der Albrecht-Thaer-Schule vor dem Holstentor in Hamburg das Abitur ab. Er war bis 1965, zunächst als Wehrpflichtiger, dann als Zeitsoldat Reserveoffizieranwärter bei der Bundeswehr.