To solve the original problem of downloading all potential dependencies without any knowledge about the state of the target machine, I suppose you could just prepare a minimal Debian installation in a container with only essential packages and run "apt-get clean && apt-get -d install $package". In principle you could then copy the downloaded package files to the target and install them offline with dpkg. You'll probably end up downloading much more than you need, though. That's inevitable without two-way communication about the state of the target.

That isn't actually a better solution than the bash and awk hacking that I'm trying to avoid though.