Souls are never actually created; here is what Krishna tells Arjuna in the Bhagavad Gita:
Never was there a time when I did not exist, nor you, nor all these kings; nor in the future shall any of us cease to be.... For the soul there is neither birth nor death at any time. He has not come into being, does not come into being, and will not come into being. He is unborn, eternal, ever-existing and primeval.
As to your question regarding what determines the experiences of a soul's first birth, Adi Shankaracharya provides an answer to this in his Brahma Sutra Bhashya: the issue never arises, because there is never a first birth for the soul. The number of births of the soul is infinite, so the karma of each birth is determined by the actions of the soul in its previous birth, going infinitely far back in time:
[F]or although the activity of the soul is not independent, yet the soul does act. The Lord indeed causes it to act, but it acts itself. Moreover, the Lord in causing it to act now has regard to its former efforts, and he caused it to act in a former existence, having regard to its efforts previous to that existence; a regressus against which, considering the eternity of the samsâra, no objections can be raised.
So to sum up, there is never a time where the soul starts out with a "blank slate" and is put in circumstances it did not deserve. The soul doesn't have a starting point, any more than Vishnu has a starting point.