Better yet, are there any Spacewalk-like software packages that work for both RedHat-based and Debian-based systems?
In addition to straight Puppet and Spacewalk, there is a puppet-based system called "foreman" that does most of what you're looking for.
while the screenshot does show CentOS and Windows clients, it does have Ubuntu support
I've used it and I recommend giving it a go.
As of 2019, Landscape on-premises is free for small installations (10 servers + 10 VMs).
Installation instructions can be found here: How do I install Landscape for personal use?
It is also open source, with source code available on launchpad.
You can try out vFense , which is still in Beta, but it supports Ubuntu, Debian, RedHat, OS X and Windows. vFense is an open source cross platform patch management tool, that is also cross referencing vulnerability data from Ubuntu, Windows, and soon RedHat as well.
Full disclosure, I am the lead developer of the project.