Step one should be to deploy a CI server, such as Jenkins. There may be some development-side work to improve this - have a good branching strategy and target your CI server at the appropriate branches, get your build process automated, incorporate any automated tests that you have into your CI pipeline.
One of the things that many (if not all) CI servers allow you to do is to have a manual promotion process. With appropriate configuration and scripting, you can incorporate both automated steps (automated testing, static analysis) as well as manual approval. If you kick off automated tests on a regular basis, you can identify every successful build. Then, with appropriate permissioning, you can allow specific users to use the web interface to tag and deploy to various levels of integration and test environments. Eventually, you can even push out production builds of your software by people promoting builds that pass each gate.
The thing that I'm not sure about is using the tool to enforce that test cases have been run. There may be appropriate plugins, but this may be a manual process. If you are using a test management tool, your CI server may plug into that and only allow promotion if a specific test suite has been marked as passing by people in a tool. It's not necessarily foolproof - people could mark as passing without actually running the tests. But I do think that you need to trust your people at the end of the day to do the right thing.
Overall, I think your strategy of choosing test cases to run based on the code changes is the right thing to do. However, I would also consider trying to invest in improving some levels of automated testing to try to find problems before it hits manual testing, but this would need to be a long-term investment and may require either training people on new skills or hiring people with certain skills.