Have you tried the easiest of them all?
sudo apt-get install gnustep
It seems like this metapackage will depend on and recommend numerous 'desktop', 'end-user' packages -- here's a portion of output of 'apt-cache show gnustep':
Depends: systempreferences.app, gworkspace.app, terminal.app, price.app | preview.app, zipper.app, textedit.app
Recommends: gnumail.app, talksoup.app, viewpdf.app, charmap.app, wmaker, gnustep-icons, gnustep-examples
Suggests: aclock.app, camera.app, timemon.app, cenon.app, poe.app, plopfolio.app, mpdcon.app, lusernet.app, grr.app, cynthiune.app, agenda.app, edenmath.app, volumecontrol.app
(The ones under 'suggests' you need to install yourself, neither apt-get not aptitude would automatically pull them in.)
For 'development' purposes:
sudo apt-get install gnustep-devel
which has the following info in 'apt-cache show gnustep-devel', and will thus deploy gorm, projectcenter and gnustep-make:
Depends: gnustep-core-devel, gorm.app, projectcenter.app
Recommends: librenaissance0-dev
Suggests: steptalk, libpantomime1.2-dev, libpopplerkit-dev, libnetclasses-dev, libaddresses-dev, libaddressview-dev, librsskit-dev, gnustep-dl2
Aside from those, there's plenty of gnustep-related packages in Debian (and therefore in Ubuntu). Listing all of the packages you can install does not seem very useful.
I also realized that you've indicated that you tried some other installation procedures, including manual ones. If that is the case, it may be non-trivial to remove GNUstep: catch various files that may have been deployed by the previous steps, remove them, and especially remove /etc/GNUstep/GNUstep.conf. If you can throw away the Ubuntu VM and start from scratch, only installing the packages as listed above, that'd be great.
If you later need to remove gnustep because you'd like to install it manually, it can be as easy as 'apt-get purge gnustep and_any_other package_here'. I'm still not going to advertise my script that builds from sources, because it's not tested recently and it's definitely not tested on 16.04.
Good luck!