This was definitely an interesting question. It seems that the only thing I've ever seen give me the "XX will be freed" output is "apt-get remove". Even more oddly, it doesn't give you that line with the -s ("dry run") command line option.
WARNING[0]: That means that using apt-get to determine the output needs to run as root. So, for the love of Bob, MAKE SURE to test it on an expendable VM first!
WARNING[1]: Make sure you know what you're doing before you start removing packages. This will go through EVERY package on the system and see how much space would be recovered (as reported by apt-get) if it were removed. This doesn't mean they are SAFE to remove. I disclaim all responsibility!
Also worth mentioning: This will likely be very, very slow. Hopefully, this is something you're looking to run situationally, as the need arises, rather than repeatedly.
That said, I offer you my final kluge of 2013. Hopefully it helps.
#!/bin/bash
for I in `dpkg --get-selections | grep install | grep -v adduser | grep -v apt | awk '{print $1}'`;
do
echo -n "$I : "
apt-get --assume-no --purge remove $I | grep "will be freed" | awk '{print $4, $5}' >> ~/package_script.out
done
I wrote and tested it under ubuntu, so it should work fine for debian et al.
Update: I added a filter to remove the adduser and apt packages from consideration. The former is too "core" to remove and takes forever, the latter locks seemingly permanently. A There are probably more packages like that...