CiviMember - Adding a premium when recording a membership payment
If these are new subscriptions only then you can create a price set where one price field contains the subscription fee and another the gifts on offer.  The back office staff would select the premium at the same time as they record the subscription payment.