Der Sohn einer Imsterin und eines britischen Offiziers entwickelte als Schüler ein Interesse für Zeichnen und Malerei. Mit 16 Jahren begann er eine Maurerlehre und besuchte von 1937 bis 1941 die Staatsgewerbeschule in Innsbruck, die er mit der Matura abschloss. Im Anschluss studierte er Architektur an der Technischen Hochschule Stuttgart, wurde aber noch im selben Jahr zur Luftwaffe eingezogen. Bei einem Einsatz als Flugmeldungsfunker bei Stalingrad wurde er 1943 schwer verletzt. Noch im Krieg setzte er sein Studium in Stuttgart fort und schloss 1945 bei Paul Schmitthenner ab. Da sein Diplom in Österreich nicht nostrifizert werden konnte, musste er die Diplomprüfung an der Technischen Hochschule Graz wiederholen. Anschließend arbeitete er von 1945 bis 1947 als Assistent Friedrich Zotters an der Technischen Hochschule Graz und besuchte die Meisterschule von Hubert Hoffmann.
1947 heiratete er die Architekturstudentin Maria Melcher, die er in Graz kennengelernt hatte. Ab 1947 war er als Lehrer an der Bundesgewerbeschule in Innsbruck beschäftigt. 1952 erhielt er die Ziviltechnikerbefugnis und eröffnete sein eigenes Büro in Innsbruck, in dem seine Frau als Büroleiterin tätig und für die Inneneinrichtungen seiner Projekte zuständig war. 1980 wurde er als HTL-Lehrer pensioniert, arbeitete aber noch bis 1993 weiter als Architekt.
Norbert Heltschl war viele Jahre Präsident der Zentralvereinigung der Architektinnen und Architekten Tirol und Vorstandsmitglied der Ingenieurskammer. Dabei setzte er sich früh für die konsequente Anwendung der Bestimmungen für Architekturwettbewerbe und Ausschreibungen ein und trug damit zur Entwicklung der Architekturszene in Tirol bei.
Zu Heltschls Werken gehören Ein- und Mehrfamilienhäuser, Freizeitbauten, Industrieanlagen, Schulbauten und Kirchen. Seine Aufträge erhielt er häufig durch den Gewinn von Architekturwettbewerben. Eines seiner bedeutendsten Werke ist das Freibad Tivoli in Innsbruck, das er als Ergebnis eines österreichweiten Wettbewerbs 1958 geplant hatte. Mit den Gebäuden aus Sichtbeton und dem wie eine Skulptur wirkenden Sprungturm gilt das (inzwischen teilweise veränderte) Schwimmbad als Zeugnis für den Anschluss Tirols an die internationale Architektur der Nachkriegszeit und steht unter Denkmalschutz. Die bildende Kunst war Heltschl wichtig und oft integraler Bestandteil seiner Bauten, insbesondere mit dem Maler August Stimpfl arbeitete er häufig zusammen.