Old version of gcc for new Ubuntu

You can use debian snapshots. Add the following lines to /etc/apt/sources.list

deb     http://snapshot.debian.org/archive/debian/20070730T000000Z/ lenny main
deb-src http://snapshot.debian.org/archive/debian/20070730T000000Z/ lenny main
deb     http://snapshot.debian.org/archive/debian-security/20070730T000000Z/ lenny/updates main
deb-src http://snapshot.debian.org/archive/debian-security/20070730T000000Z/ lenny/updates main

Now do

$ apt-get update
$ apt-get install g++-3.4

And you're set!

This works for many other old packages, make sure you select the correct timestamp, look for the correct one at snapshots.debian website.

Or alternatively to the Debian snapshots Elazar posted in his answer, you can use the Ubuntu package repositories for the older Ubuntu releases: http://packages.ubuntu.com

Add them to the /etc/apt/sources.list as Elazar already described:

deb     http://archive.ubuntu.com/ubuntu/ hardy universe
deb-src http://archive.ubuntu.com/ubuntu/ hardy universe

The Hardy Universe repository is the one that contains gcc-3.4.

You can add gcc-4.4 (or any version between 4.4 and 8) on Ubuntu 16.04 via the (Toolchain test builds PPA)

sudo add-apt-repository ppa:ubuntu-toolchain-r/test
sudo apt-get update
sudo apt install gcc-4.4

As an aside, if you need to emulate gcc-4.4 on RH6, build your target program with

make CC="gcc-4.4 -U_FORTIFY_SOURCE"