The gift-giving is actually older than Christmas itself. Much of Christmas stems from Germanic traditions, where Yule was celebrated at the time of the winter solstice. Even the Christmas tree (an evergreen) can be associated with the Germanic World Tree and the notion that life still persists in the midst of winter.
Santa Claus? Derived from the Dutch
Sinterklaas (itself a a Dutch folk name for
Sint Nikolaas; 'Saint Nicholas'), who brought the tradition to America when New York was still
Nieuw Amsterdam. But Sinterklaas is not justy based on a catholic saint: his representation owes much to Odin. That's where the gift-giving is believed to stem from: in Germanic culture, a great king showed his wealth by giving gifts. And Odin, greatest of all, king of the gods, could give gifts to all men.
There are more connections, too many to sum up, but my point is: erven without christianity ever existing, Germanic
Yule could still exist in its place, and would share many of its characteristic elements. (Which is kind of awesome, when you think about it.)
