I was wondering which of the following phrases are correct?
"without their having to learn" or "without them having to learn"?
Any help is highly appreciated.
Where a gerund-participle clause is complement to a preposition, both genitive and non-genitive subjects are possible:
I have no objections to [their/them taking notes].
She insisted on [my/me being present at the interview].
So, both your examples are fine. It's essentially a free choice between genitive "their" and non-genitive "them", though the genitive is fairly formal compared to the non-genitive.
Note that if a non-genitive subject is a personal pronoun, it always takes the accusative case ("me/him/her/us/them").