The solution to this (at least the one we've landed on at work) is to make sure your dependencies are packages in a yum repo you include on your systems. For us, that's a local private yum repo our systems have access to which we package perl Module requirements into that aren't in the public repos. We also include our private libraries there. If the utility script is commonly enough used, we'll make an RPM for is as well, or stick it in one of our general purpose utils RPMs and make sure dependencies are set. If that's done, you don't have to worry about dependencies at all, if not, you might have to manually yum install a few things that are grabbed from our yum repo.

There are lots of ways to handle this problem, but if you're handling lots of systems, you presumably already have a method you use to keep them up to date and secure. You presumably are also installing Python from the system packages (if not, you probably shouldn't be writing system utils in it unless you can ensure it's the same on every system you guys maintain, in which case your dependency problem shouldn't be a problem), so tie into that mechanism. It's a lot easier to reason about when there aren't two competing systems, and presumably you aren't going to do away with the security updates the distro provides.