'Unnatural sexual relations' for women
Lesbianism would not have been a concern for men in such a patriarchal society. The intimate relations of women, whether sexual or simply conversation, carried with it negligible power at the time: a woman's pleasure (within a marriage or not) was hardly a man's concern. There appears to be no evidence anywhere else in the bible to suggest that 'unnatural' as opposed to 'natural sexual relations' refers specifically to lesbianism or same-sex relations between women.
Nor would it likely refer to prostitution, which would have been considered a 'natural' service for men to have available - although these women had no standing in society whatsoever, they were still considered to be performing 'natural' sexual relations, as men availing themselves of this service has not deemed 'unnatural', 'perversion', 'abomination', or similar. Becoming a 'shrine prostitute' is expressly forbidden for Israelites (Deuteronomy 27:13), but foreigners or slaves becoming one is apparently not prevented, nor is making use of them expressly forbidden.
In exploring other biblical references that might condemn women for 'unnatural' sexual relations, one that comes up specifically is bestiality, which directly follows the law against (male) homosexuality:
“‘Do not have sexual relations with an animal and defile yourself with
it. A woman must not present herself to an animal to have sexual
relations with it; that is a perversion.'" Leviticus 18: 22-23
Men 'defile' themselves (suggesting impurity), whereas women commit a 'perversion' (a sexual act considered abnormal or unacceptable). Separate punishments for men and women are detailed later:
“‘If a man has sexual relations with an animal, he is to be put to
death, and you must kill the animal.
“‘If a woman approaches an animal to have sexual relations with it,
kill both the woman and the animal. They are to be put to death; their
blood will be on their own heads.'" Leviticus 20:15-16
It seems that while a man must perform the act to attract a death penalty, a woman need only approach an animal - suggesting that she can be accused of bestiality and put to death without even performing the act itself (one would imagine if her husband, betrothed, father or brother thought to make the association).
Not religious prostitution in this context
"But how worshiping gods can lead to homosexuality? I believe it must
mean religious prostitution, then it makes perfect sense."
The term 'prostitution' has indeed been used figuratively in specific reference to worshipping idols (Leviticus 20), but to draw this parallel here would be reading religious 'prostitution' in a figurative sense into the text - whereas it specifically refers to 'sexual relations'.
Paul's Letter to the Romans
Paul appears in this letter to be specifically addressing the Roman church community's judgement of the Greeks, and later their misunderstanding of the significance of Jewish law. At the time this letter was written, Paul was on his third visit to the Greek growth centres of Christianity, but had yet to visit Rome. His introduction suggests that he may be explaining his neglect of this particular growth centre for the early church:
First, I thank my God through Jesus Christ for all of you, because
your faith is proclaimed in all the world. For God is my witness, whom
I serve with my spirit in the gospel of his Son, that without ceasing
I mention you always in my prayers, asking that somehow by God's will
I may now at last succeed in coming to you. For I long to see you,
that I may impart to you some spiritual gift to strengthen you— that
is, that we may be mutually encouraged by each other's faith, both
yours and mine. I do not want you to be unaware, brothers, that I have
often intended to come to you (but thus far have been prevented), in
order that I may reap some harvest among you as well as among the rest
of the Gentiles. I am under obligation both to Greeks and to
barbarians [non-Greeks], both to the wise and to the foolish. So I am
eager to preach the gospel to you also who are in Rome.
For I am not ashamed of the gospel, for it is the power of God for
salvation to everyone who believes, to the Jew first and also to the
Greek. For in it the righteousness of God is revealed from faith for
faith, as it is written, “The righteous shall live by faith.” Romans
Paul's connection between idolatry and sins of the flesh
He then goes on to makes a connection between idolatry and these many and varied sins of the flesh suggesting that one act may inevitably lead to the other. But he also points out that both the society he addresses (Romans) and 'them' who are judged (ie. Greeks), by practising idolatry, have so far not seen fit to acknowledge God, who has therefore 'given them up to a debased mind to do what ought not to be done'.
It may be significant to note that most documented instances of bestiality involving women around the time the NT was written were found to be either ritualistic or involved the worship of gods, including the Greek legends of women performing sexual relations with 'gods' in animal form, eg. swan, bull, etc). Likewise, homosexual relations were found to be an accepted norm in Greek society at the time. The young male nude was worshipped in Greece as a symbol of perfection, and adolescent boys were regularly 'courted' to submit to an elder sexually in exchange for knowledge.
So this initial description of 'shameful lusts' may be attributed specifically to Greek society, setting 'them' apart in judgement by the Romans. But the next section describes sin that the Romans certainly cannot declare themselves free from in their own society:
And since they did not see fit to acknowledge God, God gave them up to
a debased mind to do what ought not to be done. They were filled with
all manner of unrighteousness, evil, covetousness, malice. They are
full of envy, murder, strife, deceit, maliciousness. They are gossips,
slanderers, haters of God, insolent, haughty, boastful, inventors of
evil, disobedient to parents, foolish, faithless, heartless, ruthless.
Though they know God's righteous decree that those who practice such
things deserve to die, they not only do them but give approval to
those who practice them. Romans 1:26-32
Paul makes continual reference later in this letter to the dual influences of the flesh and the spirit on our actions:
Those who live according to the flesh have their minds set on what the
flesh desires; but those who live in accordance with the Spirit have
their minds set on what the Spirit desires. The mind governed by the
flesh is death, but the mind governed by the Spirit is life and peace.
The mind governed by the flesh is hostile to God; it does not submit
to God’s law, nor can it do so. Those who are in the realm of the
flesh cannot please God. Romans 8:5-8
For Paul, either we are striving to live by the spirit - rejecting sin as 'what the flesh desires' - or we are living by the flesh, ruled by sin (or by the law which cannot defeat sin) and by death.
He leads into the dichotomy in this first chapter: either we strive to be wholly committed to God and life in the spirit, rejecting the worship of idols, or we turn our face from God and are thereby 'given over' to be commanded by the flesh instead of by the spirit.
At the start of the second chapter, therefore, Paul makes it clear that those he addresses, who apparently judge 'someone else' (ie. the Greeks) by their 'shameful lusts', do the same things (sin in the flesh) and are given over to be ruled by sin because they also practise idolatry.
You, therefore, have no excuse, you who pass judgment on someone else,
for at whatever point you judge another, you are condemning yourself,
because you who pass judgment do the same things. Now we know that
God’s judgment against those who do such things is based on truth. So
when you, a mere human being, pass judgment on them and yet do the
same things, do you think you will escape God’s judgment? Or do you
show contempt for the riches of his kindness, forbearance and
patience, not realizing that God’s kindness is intended to lead you to
repentance? Romans 2:1-4
Here, Paul suggests that worshipping idols - tantamount to rejecting God - is a first step towards being ruled by sin. So those who worship idols and yet pass judgement on others who commit any of these sins have essentially turned away from God - ie. done the same thing as those sinners (the Greeks) whom they apparently judge.
While there is no evidence to support the interpretation of 'unnatural sexual relations' performed by women to specifically mean either lesbianism or prostitution, there are suggestions in Jewish law that it may in fact mean bestiality - considered a perversion in women (while only impure in men).
Paul's connection between worshipping idols and these specific 'shameful lusts' of bestiality by women and homosexuality by men is supported by historical evidence of both acts in connection with Greek mythology and customs.
While the passage agrees with the condemnation of these acts according to Jewish law, Paul's intention is not to reiterate these laws, but to point out that the Romans and those they judge for these 'shameful lusts' are in fact both in need of repentance.