The Gemara definitely says that the city was entirely female. However, a Midrash (Bereishis Rabbah 33:1) seems to discuss the same journey and indicates that males lived there as well (translation and boldfacing is from Artscroll):
אֲלֶכְּסַנְדְּרוֹס מוֹקְדוֹן אֲזַל לְגַבֵּי מַלְכָּא קַצְיָא לַאֲחוֹרֵי הָרֵי חשֶׁךְ, וּשְׁלַח לֵיהּ, נְפַק לֵיהּ וְהוּא טָעֵין גִּדּוּמֵי דִּדְהַב בְּגוֹ דִּסְקוּס דִּדְהַב, אֲמַר לֵיהּ לְמָמוֹנָךְ אֲנָא צְרִיךְ. אֲמַר לֵיהּ וְלֹא הָיָה לְךָ מַה מֵּיכוֹל בְּאַרְעָךְ דַּאֲתֵית לָךְ לְהָדֵין
Alexander of Macedonia went to see a king at the other end of the world, beyond the Mountains of Darkness. [The king] came out to greet [Alexander], and he was carrying golden loaves in a golden tray. [Alexander] said to him, "Do you think that I came here because I need your money?!" [The king] responded, "If so, did you not have what to eat in your own land that you needed to come to this far-off land in search of food?"
So far, the Midrash is very similar to the Gemara (skipping the part about Alexander waging war on them), except that apparently the city of women (a detail the Midrash doesn't note) has a king, not a queen.
We see from the continuation of the Midrash that the king wasn't the only male in the city:
, אֲמַר לֵיהּ לָא אָתֵית אֶלָּא בָּעְיָא לְמֵידַע הֵיךְ אַתּוּן דָּיְנִין, יְתִיב גַּבֵּיהּ, יוֹמָא חָדָא אָתָא חַד בַּר נָשׁ קֳבֵל עַל חַבְרֵיהּ, אֲמַר הָדֵין גַּבְרָא זַבַּן לִי חָדָא קִלְקַלְתָּא וְאַשְׁכָּחִית בְּגַוָּהּ סִימְתָא, הַהוּא דְּזָבִין אֲמַר קִלְקַלְתָּא זַבְּנִית סִימְתָא לָא זַבְּנִית, וְהַהוּא דְּזַבַּן אֲמַר קִלְקַלְתָּא וּמַה דִּבְגַּוָּהּ זַבֵּנִית. אֲמַר לְחַד מִנַּיְיהוּ אִית לָךְ בַּר דְּכַר, אֲמַר לֵיהּ הֵין. וַאֲמַר לְאוֹחֲרָנֵי אִית לָךְ בְּרַתָּא נֻקְבָא, אֲמַר לֵיהּ הֵין. אֲמַר לְהוֹן זִיל אַסֵּיב דֵּין לְדֵין וַהֲוֵי מָמוֹנָא לְתַרְוֵיהוֹן.
[Alexander] said to him, "I came here only because I wanted to learn how you dispense justice." So [Alexander] sat near [the king] to observe how he judges the people. One day, an individual came before the king and presented a complaint against his friend. He said to the king, "This man sold me a ruin, and in it I discovered a treasure." The individual who purchased the ruin said to the king, "I did not purchase a treasure, and I do not wish to keep it." And the individual who sold the ruin to his friend said, "I sold the ruin and everything that is inside it, and I want you to keep the treasure." [The king] said to one of them, "Do you have a male child?" [The man] answered, "Yes." [The king] then said to the other one, "Do you have a female child?" [The man] responded, "Yes." [The king] said to them, "Go and marry off this girl to this boy, and the monetary value of the treasure shall belong to both of them."
How do we resolve this contradiction? I find it hard to believe that there's multiple cities beyond the Mountains of Darkness which Alexander visited, which all greeted him with golden loaves and the same rationale for doing so. Which leaves one of several possibilities:
- The city initially gives the appearance of being of women, in order to dissuade any would-be attackers (as the Gemara describes). Once they're sure that the visitors won't attack them, the men come out as well.
- When the Gemara says that the city was entirely female, it means that it was mostly female (as often a majority is considered an entirety). The fact that most of the residents were women was enough for their argument of "you'd be called a women-killer" to take hold (perhaps it was a large majority).