nathalia, in Victoria there are heaps of cycletouring clubs. I presume there are lots in Queensland too. Join a cycletouring club, get to know some of the members, and then go to Asia with someone who is compatible with you.

Speaking as a female cycletourist, I wouldn't want to go on an extended tour with a complete stranger. What if you discovered that you and the complete stranger did not get along at all within the first few days of the tour?