It is not possible for there to be a human language that does not have a way of referring to entities, or to predicate states and actions of an entity. If that is what you mean by "noun" and "verb", then all languages have nouns and verbs. However, noun, verb, adverb, adjective are typically treated by linguists as "word classes", defined in terms of how they are structured or function with other word classes (and not in terms of what they mean), and it is (at this point in linguistic theory) not entirely clear that the distinction is vital. For example, Salishan languages are flexible in noun / verb relations, so a root may be more noun-like with a certain prefix, and more verb-like with a different affix (suffix, in Lushootseed). Nouns and verbs both have past and future tenses. One can typically discern, on a language specific basis, some formal basis for calling certain words "nouns" versus "verbs", such as "adding s- makes this a noun", but it may not yield any significant benefit to making such a distinction. The formal properties of English nouns, verbs and adjectives do not define an "architype" for such words in most languages.
One way of understanding the underlying issue is that there are two different questions you can ask about word classes. One is whether there is always compelling evidence in all languages for distinguishing nouns and verbs (or verbs and adjectives), and the answer to that is "No"; but, you can also ask if it is always possible to define such a distinction in a language, on the premise that there might be mandatory but not particularly useful categories of analysis, and the answer to that is "Yes" (but IMO this begs the question of whether there are mandatory categories in grammar).