[This answer is only about the linguistic-method side of the question (I’m a linguist); the “have there ever been two groups that couldn’t communicate?” question, I can’t speak to].

The short-form answer is that you do a very, very organized (and repetitive) process that involves taking visible, manipulable objects (rocks, leaves, food items) and counting on a — hopefully kind and patent — speaker of the other language to catch on that you’re wanting them to say the word for what you’re holding up or pointing at. There are all sorts of ways this can go wrong in individual cases (you hold up a leaf and the other person actually says “That person’s never seen a leaf before?”), but when you get some nouns figured out, you can do hypothesis-testing with them: say a word and see if the speaker points at or hands you what you’re expecting. Of course, early on you might mangle the pronunciation too much for the other person to understand it, but you get the idea — over time, you keep the guesses that worked and toss out the ones that don’t. The key is to set up situations where, to the extent it’s possible, both parties have a high chance of knowing what approximate meaning is being conveyed based on non-linguistic cues (if you’re holding up a rock and pointing at it, what you’re saying is highly likely to be about that thing you’re holding, although there are still lots of different nuances you can’t predict). Miming simple actions can then get you some potential verbs and so forth. Everything you figure out then helps you figure out more. Once you get “I’m moving the rock” (or something sort of like that), you then repeatedly move a leaf, then something else, and see what you get.

As for how long that takes…well, with a very cooperative person willing to spend a lot of time working with you, and basic vocabulary & simple sentences, a month or two might give you a good basis for bartering simple goods, communicating basic directions, making simple polite requests, etc. People with really good memories and a good sense of social interaction might be faster, but it’s not a quick process. You’re not going to be doing much with abstract or philosophical discussion without a lot more time although you might use analogies to approach kinda-complex topics (until the analogy breaks, which it inevitably will). Any translation needs to be read with an implicit “The translator thinks the speaker said something like the following:…” at the beginning, and with any kind of “new contact” scenario, that becomes profoundly important.

Linguistics has developed a bunch of concepts that helps with this (knowing that some patterns that are more likely than others can let you make more informed guesses), but the core of the methodology really is based on repetitive elicitation and hypothesis-testing that anyone with a good memory and a high tolerance for tedium can manage. For a detailed account, albeit one that uses modern terminology, I’d suggest looking at Vaux, Cooper, & Tucker’s Linguistic Field Methods. For a video demo of the process, Daniel Everett has a youtube video you might find helpful.