Virtually all Men were indeed under the domination of Sauron, and the Last Alliance was chiefly made between the Elves and the realms of the surviving Faithful Númenóreans, as is told in "Of the Rings of Power and the Third Age":
Now Sauron prepared war against the Eldar and the Men of Westernesse, and the fires of the Mountain were wakened again [...] And Sauron gathered to him great strength of his servants out of the east and the south [...]
The formation of the Last Alliance is also described:
Now Elendil and Gil-galad took counsel together, for they perceived that Sauron would grow too strong and would overcome all his enemies one by one, if they did not unite against him. Therefore they made that League which is called the Last Alliance, and they marched east into Middle-earth gathering a great host of Elves and Men; and they halted for a while at Imladris [...] From Imladris they crossed the Misty Mountains by many passes and marched down the River Anduin.
It should be obvious from this passage that the "march east" was actually just through Arnor, a Númenórean realm which had been founded by then (note that the Alliance turned south after Rivendell, so the "march east" is just from Lindon to Rivendell).
Although I don't have a reference for it, I would expect that the Northmen of Rhovanion, as descendants of the Edain who never crossed over to Beleriand but who despite that had also rejected Morgoth in the First Age, were also included in the Alliance.
It was only after the victory of the Alliance that Men who were under Sauron's domination rejected it:
The servants of Sauron were routed and dispersed, yet they were not wholly destroyed; and though many Men turned now from evil and became subject to the heirs of Elendil.
But as we know, the Númenórean faithful were never under the domination of Sauron, and Arnor and Gondor had already been founded by the time of the Last Alliance, and — although new realms — appear to have become quite strong in a short time. Gondor in particular is described as follows:
Isildur and Anárion were borne away southwards, and at the last they brought their ships up the Great River Anduin, that flows out of Rhovanion into the western sea in the Bay of Belfalas; and they established a realm in those lands that were after called Gondor, whereas the Northern Kingdom was named Arnor. Long before in the days of their power the mariners of Númenor had established a haven and strong places about the mouths of Anduin, in despite of Sauron in the Black Land that lay nigh upon the east. In the later days to this haven came only the Faithful of Númenor, and many therefore of the folk of the coastlands in that region were in whole or in part akin to the Elf-friends and the people of Elendil, and they welcomed his sons.
So there were definitely no shortages of allies for the Alliance.
