During the process of star formation, the dense gas undergoes significant chemical evolution leading to the emergence of a rich variety of molecules associated with hot cores and hot corinos. However, the physical conditions and the chemical processes involved in this evolution are poorly constrained. In particular, the early phases, corresponding to a stage prior to the emergence of any strong ionising emission from the protostar, are still poorly studied. In this work, we provide a full inventory of the emission from complex organic molecules (COMs) to investigate the physical structure and chemical composition of six high-mass protostellar envelopes. We aim to investigate the conditions for the emergence of COMs in hot cores. We performed an unbiased spectral survey towards six infrared-quiet massive clumps between 159GHz and 374GHz with the APEX 12m telescope, covering the entire atmospheric windows at 2mm, 1.2mm, and 0.8mm. To identify the spectral lines, we used rotational diagrams and radiative transfer modelling assuming local thermodynamic equilibrium. We detect up to 11 COMs plus three isotopologues, of which at least five COMs (CH_3_OH, CH_3_CN, CH_3_OCHO, CH_3_OCH_3_, and CH_3_CHO) are detected towards all sources. Towards all the objects, most of the COM emission is found to be cold, with respect to the typical temperatures at which COMs are found, with a temperature of 30K and extended with a size of ~0.3pc. Although the bulk of the gas for our sample of young massive clumps has a cold temperature, we also detect emission from COMs originating from the immediate vicinity of the protostar. This warm component of the envelope is best traced by methanol and methyl cyanide, in particular methyl cyanide traces a compact (~1") and the hottest (T~200K) component of the envelope. Only three out of the six sources exhibit a robustly detected hot gas component (T>100K) traced by several COMs. We find a gradual emergence of the warm component in terms of size and temperature, together with an increasing molecular complexity, allowing us to establish an evolutionary sequence for our sample based on COMs. While they can already be well characterised by an emerging molecular richness, gas temperatures of COMs in the hot gas and molecular abundances suggest that COMs may become abundant in the gas phase at temperatures below the thermal desorption temperature. Our findings confirm that the sources of our sample of infrared-quiet massive clumps are in an early evolutionary stage during which the bulk of the gas is cold. The presence of COMs is found to be characteristic of these early evolutionary stages accompanying high-mass star and cluster formation. While the extent of the compact heated regions resembles that of hot cores, the molecular abundances, except for complex cyanides, resemble those of hot corinos and are lower than the peak COM abundances of hot cores. We suggest that the emergence of hot cores is preceded by a phase in which mostly O-bearing COMs appear first with similar abundances to hot corinos albeit with larger source sizes.