How did the first human to learn two languages (assuming s/he did) do it? How could two peoples who can't communicate with language exchange languages?

The same way you would pick up a foreign language when travelling, not having a dictionary.

You'd point at things and learn the local name for it. Then between hand gestures and context, you'd pick up the rest.