By the literal meaning, "free gift" is a pleonasm, but as the word is actually used, a free gift is distinct from a gift. Anywhere I have seen the phrase, the recipient had to pay for a "free gift".