You're right... that is complex ;)

As far as I'm aware it is not possible, and would require a custom dev quote.

The closest you could get using existing functionality would be to automatically add specific free products to the cart if 3 of a category were already in the cart. The part that is not possible (as far as I'm aware) is to give customers the choice of which free items they want.

Cheers