Our discount feature only deals in actual products and prices, so there are two ways to approach this:
First would be to create a product that has a cost, but also distribute a coupon code that waives the full cost so that the item can be ordered for $0.00. Or just create an item that costs $0.00! That will allow a free gift to be added to any order.
The other option requires more programming work outside of our cart, but it is possible to pass a custom value along with your order. You could set something up on your site to ask for the "free gift code" and then save the value that buyers type in. You can also set your site up to reject the wrong codes.
Then, that custom code can be passed along through your orders as described in our help pages here (see the part on passing a custom variable for a full order):
Setting your page up to send that variable to us would be tricky, but it would also give you a simple flag on each order that allows you to see who should get a free gift or not at a moment's glance, and you don't need to set the gift up in your account as an actual item.