I currently have a contract which requires around 16M gas to deploy and execute. Trying to deploy using Parity on Kovan net fails due to gas limit being reached. On my private network I just configured the gas limit of the test server to match my needs, however I assume this won't help when it comes to deploying to an actual network since other miners have lower gas limit settings and since we need a consensus contracts like these simply can't be deployed?
Correct, contracts like these can't currently be deployed, although it may become possible to deploy them in future if and when miners raise the gas limit.
16M gas sounds like a very big contract; You may want to consider breaking it up into a number of smaller ones.