However I note that the analogRead function does not do it this way. My reading of the datasheet suggests that the MUX settings are continuously copied into the temporary register used during an ADC conversion. Then when the conversion starts, in the first ADC clock cycle, the MUX value is latched into the temporary register (so it is used from then on during the conversion).
Thus, if a conversion is not in progress, and you are not using auto-triggering, then it should be safe to change the MUX input before starting the conversion.