So, with credit to the Factorio wiki and cbednarski's helpful gist, I managed to eventually setup a Factorio headless server. Although, I thought the process could be nailed down/simplified to be a bit more 'tutorialised' and also to document how I got it all working for my future records.
The specific distro/version I'm using for this guide being Ubuntu Server 16.04.1 LTS. Although, that shouldn't matter, as long as your distro supports systemd (just for this guide, not a Factorio headless requirement, although most distros use it as standard now).
The version of Factorio I shall be using is 0.14.20, although should work for any version of Factorio 0.14.12 and higher.
Just a note to newcomers: If there are any issues with the installation steps, people in the comments are doing a good job