TL;DR Roll out a container orchestrator for new builds (e.g. OKD or the commercial version OCP). Work on packaging existing apps to be managed by an automation system (e.g., Puppet Enterprise) so rollout, patching and upgrades are all automated. Take root access away from everyone else and have them only do installs via the automation tools.
Long Answer including one fully automated WMWare private cloud:
Moving to cloud native tech such as Kubernetes, CloudFoundry or Docker Swarm isn't an easy option if you have a huge set it existing apps. Yet you could potentially reap huge benefits from making such technology available for new development. What you want is for teams to "self-service" via, say, the Kubernetes webui and command line tools. OKD is a distro of Kubernetes that focuses on “self-service devops” that I have seen work very well for three large system builds at three large organisations. It can be installed on Linux VMs that you manage any way you want (e.g., Puppet Enterprise example below) and there is commercial support from a large Linux vendor.
With such an approach you setup a cluster you can expand to up to 2000 identical VMs. You grant teams a logical “namespace” (aka “project”) and assign a quota for memory and cpu. Teams then use the webui or command line to spin up dozens of containers that are automatically spread over the cluster of VMs. You can apply tags to VMs and projects to place different teams on different pools of VMs if you still want bill departments based on how many VMs they reserve. OKD does software defined networks and automated DNS for each project so it takes away the headaches of assigning IPs or managing DNS as it is fully automated. Also load balancing, fail-overs and scale out are all automated. It also does rolling deployments and will health check containers and restart failed ones.
New apps will need to be built to modern standards to work within such a container orchestrator. In four separate experiences of rolling this out I have seen skeptical developer teams love the immediacy of "just help ourselves" up to their quota. The forget they ever started out demanding root access. I worked at a big organisation where we automated setting up each new scrum team with with multiple environments on commercial OKD (called OCP) with databases, networks, git repos, and running sample code all created by a small webapp we wrote in less than 15 minutes.
With your existing stuff then the road out of cost and overhead is standardisation, standardisation and more standardisation. At the moment I am working with a private cloud platform which is VMWare vRA based. The vRA portal has blueprint that internal customers launch standardised host profiles for databases, message brokers, webservers and "vanilla” (plain) Linux hosts. The launched images have Puppet Agent installed and a Puppet Enterprise Server enforces, you guessed it, standards. If you use root to tamper with the config then puppet agent runs every 20 minutes and puts back the configuration to match the puppet profile.
The puppet profiles are all in git and a separate Puppet Hiera config repo defines all configuration setting for all hosts. One git repo has the Hiera config for the base OS with different overrides for database profiles or application profiles (eg applying kernel settings). A second git repo holds the Hiera config for the application profiles (e.g., install and start oracle database, or a message brokers, or a web server). A third repo holds the Hiera config for any host level overrides needs for tricky applications or production fixes yet to make it into the main configuration for that application profile.
Puppet chooses the most specific configuration settings for the actual hosts. It looks for host specific, not normally needed, then looks for app profile specific settings, not always defined, then uses the default for the OS. Everything is in git and managed by code review of pull requests. It’s proper infrastructure-as-code managed by GitHub Enterprise.
All of the above works for the “standard” software packages used at the organisation. For in-house apps they don’t yet have Kubernetes. Teams launch a “vanilla” Linux blueprint on the VMware vRA portal rather than a specific application blue print. So they might launch an Oracle database blueprint and three vanilla Linux ones to run their java code. With vanilla it has all the access management packages (Centify) and teams just run use scp to upload their java. Teams are using Ansible Tower to upload their Java apps via none root ssh access. That is driven by Jenkins deploy jobs that call out to Ansible Tower.