Родился в семье лесного бракёра, по национальности балтийского немца, мать Серафима Арсеньевна (урожденная Шестова) — русская.
Во время Великой Отечественной войны Генрих Шульц служил писарем в 8-м Эстонском стрелковом корпусе Красной армии. Он участвовал в наступлениях в районе реки Эмайыги и в Моонзундской операции, а также в боях в Курляндии (1944—1945).
С 1961 по 1967, в качестве руководителя отдела культуры Таллинского Исполнительного комитета Совета депутатов трудящихся (в настоящее время Департамент культуры Таллинской городской управаы), он также организовал международные джазовые фестивали, танцевальные турниры и другие культурные мероприятия. Самый крупный и наиболее известный из них, Таллинский Международный джазовый фестиваль «Таллин-67» ("Tallinn-67"), состоявшийся в мае 1967 года, стал легендарным. Участвовали известный квартет Чарльза Ллойда из США, джазовые коллективы из Эстонии, Латвии, Литвы, России, Украины, Азербайджана, Грузии, Швеции (секстет Арне Домнеруса с Яном Йоханссоном на фортепиано), а также Финляндии и Польши.
Это событие привлекло значительное международное и внутригосударственное внимание средств массовой информации и напугало власти в такой степени, что джазовые фестивали были запрещены, как угроза существующей коммунистической идеологии. Всю «вину» за организацию фестиваля возложили на Генриха Шульца, и впоследствии он был уволен с поста начальника отдела культуры.
В течение десятилетий Генрих Шульц жил в безвестности, ему было запрещено занимать ответственные должности. Начиная с перестройки, средства массовой информации стали говорить о его вкладе в организацию джазовых фестивалей, как уникальных культурных столкновении между Советским Союзом и Запада в период холодной войны.