I'm having trouble remembering if bitcoind/bitcoin-qt prioritized older coins (high coin age) or fewest inputs (least tx size).  I don't THINK it will automatically figure out the way to make one qualify for no fee.

Unfortunately, I'm not familiar enough with 3rd party wallets to identify which ones (if any) will let you pick which inputs to use for making your transaction, or if any of them have been designed to attempt to prioritize making a transaction qualify for no-fee.