In the U.S. where I live it is possible to be right almost all of the time when guessing the sex of a person from his or her given name: Ronald, George (Sand and Elliot notwithstanding), William, Michael (Learned notwithstanding), Warren and Chuck are all men's names, while Emily, Christine, Jasmine, Nancy and Camille are obviously female. Some nicknames go both ways (Chris, Sandy, Sam, etc.) but the full names are generally obviously on one side or the other.
In German, generally nobody thinks Karlheinz is female or Gisele is male. Cf. Spanish (Juan, Juanita, etc.), French (Michel, Michelle) and so on. Even in Latin, it was possible to tell Julia and Julius apart by letters alone.
Some languages have markers to indicate gender (see this Linguistics.SE question. That question discusses PIE affixes, but the scope is even broader. For example, in Japanese, -o or -ro endings indicate male names, while -ko and -e indicate female names. Note that my question is not limited to the scope of that question.
I don't know all the languages that have ever existed in the world, obviously, but all of the ones I have had contact with make a more-or-less clear gender distinction with given names. Are there or have there ever been languages that didn't make this distinction?