Non-existent problem, and that's why you've proposed this terrible, centralized, trust requiring solution. The simplest way to hand over some coins to somebody without him having a wallet software downloaded is to give him a paper wallet with the corresponded instructions.

I don't understand why you'd want to give bitcoin to someone who doesn't have a wallet software. If he doesn't know it at all, it's likely that he'll screw things up. Also, giving money as a gift defeats the gift part. But, if you want to, the safest option is the paper wallet.