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 2015, Landscape 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: https://launchpad.net/~landscape/+archive/ubuntu/15.01
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. The github link for the project is http://github.com/toppatch/vFense.
Full disclosure, I am the lead developer of the project.