We present the average rest-frame spectrum of high-redshift dusty, star-forming galaxies from 250-770GHz. This spectrum was constructed by stacking ALMA 3mm spectra of 22 such sources discovered by the South Pole Telescope and spanning z=2.0-5.7. In addition to multiple bright spectral features of 12CO, [CI], and H2O, we also detect several faint transitions of 13CO, HCN, HNC, HCO+, and CN, and use the observed line strengths to characterize the typical properties of the interstellar medium of these high-redshift starburst galaxies. We find that the 13CO brightness in these objects is comparable to that of the only other z>2 star-forming galaxy in which 13CO has been observed. We show that the emission from the high-critical density molecules HCN, HNC, HCO+, and CN is consistent with a warm, dense medium with T_kin ~ 55K and n_H2 >~ 10^5.5 cm^-3. High molecular hydrogen densities are required to reproduce the observed line ratios, and we demonstrate that alternatives to purely collisional excitation are unlikely to be significant for the bulk of these systems. We quantify the average emission from several species with no individually detected transitions, and find emission from the hydride CH and the linear molecule CCH for the first time at high redshift, indicating that these molecules may be powerful probes of interstellar chemistry in high-redshift systems. These observations represent the first constraints on many molecular species with rest-frame transitions from 0.4-1.2mm in star-forming systems at high redshift, and will be invaluable in making effective use of ALMA in full science operations.