There is no means to think without language.
There is no means to think with language. Language has no problem solving capability. (Assuming you mean language as in natural language; if you're broadening the term to include all forms of symbolic representation, then it's a different matter).
What's more there is no evidence that language shapes thought (with one exception, knowing a specific word for a colour does produce a measurable effect in the ability to remember that colour) and many simple demonstration that we
don't think in language: ever not had the word to express what you're thinking? Ever come across a new word and realised it describes exactly what you wanted to say? How about animals? We know many animals that can't speak, or understand language, yet they are capable of quite impressive intellectual feats.
Otherwise, you have a mostly non-functioning organ that just keeps increasing for no reason until one day: BAM, language... seems silly. Now, at what point the 'internal' language actually became externally used for communication, I haven't a clue.
Imagine this instead: language evolved from simpler forms of communication. We know simpler forms of communication exist because they're used throughout all forms of life on earth, from bacteria to dolphins. Some are auditory, some are visual, some are olfactory. Among our nearer relatives the monkeys and the great apes there are even some with basic pseudo-grammars. The advantage to greater levels of communication are fairly obvious and pretty linear. Try this simple experiment: go to France (assuming you don't speak French) and try to get around. To begin with you'll only know a few words and have to point and gesture and be unable to get your point across in many cases. Learn a few more and things become easier. A few more and it gets easier still. The same principle applies with the evolution of language.
™ Version 4.2