Apologies in advance for the long read, but I tried to answer the question fully.
Assuming that we magically have the ability to synthesize the chemicals individually, then with sufficient ventilation this should be possible. I'm ignoring the nitty gritty details of creating a scent and clearing it from the area once it's been smelled. Let's also assume they're blind or near-blind too but have developed means of finding one another, as this narrows us to haptic and olfactory communication.
Since we are dealing with deaf and blind humans, the senses of touch, smell, and taste will become much, much more sensitive due to the lack of visual and auditory input. This does a number of useful things: Firstly it justifies the ability to distinguish smells better than we do now, and secondly it means that we are likely to have developed haptic alternatives to things we now do visually and auditorily, most notably identifying the person you're interacting with by the shape and texture of their hands and face. These things happen already with dead and blind people, so it is not beyond the realm of possibility. The only bottleneck will be how quickly you could clear a given smell from the air, which could be largely nullified by having a source of 'unscented' air, either from an artificial source such as compressed air in a SCUBA-like configuration, or from natural airflow, though this could one conversation overly 'loud' to those downwind, making them unable to hold their own conversation, so my preferred solution would be clearing the nasal canal with pre-filtered compressed air, possibly with some circular breathing involved...
Now on to the actual communication. I'm taking into account the article you added to your question and using their most conservative figure, 4,500 distinguishable smells. Normal human language's smallest discrete unit is the phoneme, an individual sound. The sounds available in a given language, and the possible combinations of them into syllables and syllables into words, determines the limit of what can be produced by that language. Since smells don't have the same substructures of consonants and vowels, we are actually free of a lot of the restrictions of human language. In addition, the language with the largest number of phonemes in the world is the Taa language, with ~90 consonants and ~30 vowels (ignoring changes in tone), making a total of approx. 120 distinct sounds. We, on the other hand, have 4,500 building blocks with which to work. This means that with each 'scenteme' (I'm using this as a term for an individual smell, by itself) we can convey 37 times more information than in a maximally dense human language. Furthermore, there is nothing preventing combinations of different scents, where the human mouth can only produce one sound at a time! The limiting factor as to whether or not something can be used to form a language is how much information you can transmit with it in a given amount of time. If that limit is higher than human language, you're good to go. I believe we have met this requirement.
As for the structure of the language, there are two obvious paths: highly fusional, or highly isolating. I'll handle these separately.
Isolating would be taking a route similar to Chinese, whereby each word is always the same, and each syllable is represented by one character. Applied to this situation, this would mean having a meaning or grammatical function attached to each scenteme, giving you a base vocabulary of 4,500 'words', and for anything more complex you can combine subconcepts either one after the other or simultaneously to produce a new compound 'scentyllable'. Let's assume the language is constricted to one scenteme at a time, since we are already dealing with the theoretical limit of human perception, and adding more would be attempting to go beyond that limit. I think one could actually adapt Chinese to this pretty well, so for details on such an implementation, I recommend looking at Chinese grammar.
A fusional approach would be doing something similar to Indo-European languages, with roots and inflections, where verbs conjugate and nouns may inflect for gender, case, and number. This is the less trivial approach, but more interesting, as you can have a scenteme being part of many different roots, conjugation affixes, prepositions, etc. For this I would look at Ancient Greek and Finnish, as the one has a large case system and the other a large system of tenses. What's nice with Ancient Greek is that it has high information density in its conjugations, so following that example with a scenteme inventory of 4,500 elements would have even greater success, as where Greek runs out of letters and has to combine, this language can just keep going, and will only have to begin making combinations of scentemes in much more specific cases. In fact, you could be liberal with your use of scentemes and use one to indicate what those that follow will indicate. For example, let's assume 100 separate parts of speech to be generous. In this case, scenteme #1 could indicate that the next scenteme will be a single-scenteme-root, and #2 could indicate a double-scenteme-root (two scentemes in a row), and #3 could indicate a conjugation, while #4 could indicate a preposition, and so on. The space available for roots is then from scenteme #101 to #4500. With single and double scenteme roots, this allows 19,364,400 possible roots, more than enough for human communication even without any kind of derivational morphology.
So, there are many ways to go as far as the structure of the language is concerned, but both of these extremes will satisfy and even exceed the requirements for human communication. In fact, one could adapt Ithkuil to this and be able to represent almost any possible thought in very little space.
I hope this helps!
