The BL Lac object S5 0716+71 was observed in a global multi-frequency campaign to search for rapid and correlated flux density variability and signatures of an inverse-Compton (IC) catastrophe during the states of extreme apparent brightness temperatures. The observing campaign involved simultaneous monitoring at radio to IR/optical wavelengths centered around a 500-ks INTEGRAL pointing (November 10-17, 2003). We present the combined analysis and results of the cm- to sub-mm observations including a detailed study of the inter- to intra-day variability and spectral characteristics of 0716+714. We further constrain the variability brightness temperatures (T_B) and Doppler factors (delta) comparing the radio-bands with the hard X-ray emission (3-200 keV). 0716+714 was in an exceptionally high state (outburst) and different (slower) phase of short-term variability. The flux density variability in the cm- to mm-bands is dominated by a correlated, ~4 day time scale amplitude increase of up to ~35% systematically more pronounced towards shorter wavelengths. This contradicts expectations from standard interstellar scintillation (ISS) and suggests a source-intrinsic origin of the variability. The derived lower limits to T_B exceed the 10^12 K IC-limit by up to 3-4 orders of magnitude. Assuming relativistic boosting, we obtain robust and self-consistent lower limits of delta >= 5-33, in good agreement with delta_VLBI obtained from VLBI studies and the IC-Doppler factors delta_IC > 14-16 obtained from the INTEGRAL data. Since a strong contribution from ISS can be excluded and a simultaneous IC catastrophe was not observed, we conclude that relativistic Doppler boosting naturally explains the apparent violation of the theoretical limits within standard synchrotron-self-Compton (SSC) jet models of AGN.