You don't have to have an embassy to be able to talk to another civ. At first contact between land units of your civ and the opposing civ they will request an audience automatically. From that moment you will be able to request an audience by entering yhe foreign advisor screen (F3), and choose which civ you want to talk to. If you have established an embassy with a civ or if you have a working Marco Polo or UN you will also be able to check the intelligence of a civ. This will give you knowledge of how many cities they have, government, capital, what they're researching and all their techs. What you are told depends on what level you're playing.
So, unless you have UN or Marco Polo, you will be able to request the audience of any civ you've met with landunits in the foreign advisor screen.