Some clarification:
There is no bitcoin wallet software on the LiveCD. Only software to generate keys and QRs and print them on wallets. The goal is to print wallets without ever having their keys be online or seen by an online system that may have trojans.
Sounds good. As long as users are aware that they are exposed to trojan the day when they need to load the private key in order to spend their bitcoins. But meanwhile, it is indeed a nice way to deposit bitcoins to a Bitcoin address securely.
If I understand correctly, the issue of "change" only occurs if people try to redeem small amounts of a wallet, not the complete balance of that address, right?
Indeed. Any transaction not spending the entire amount needs to send the change back to a Bitcoin address (otherwise the whole change would become the transaction fee). Many Bitcoin clients don't send the amount to the source address. They send the change to a random new address that is stored in the wallet. As such, if your paper wallet was loaded in Bitcoin-Qt or Multibit in order to spend only a part of the funds available on the paper wallet, there are good chances that such a transaction would transfer all remaining funds without the user being aware of it (because it's not really intuitive).