How much time to I have to switch outputs on a CD74HC4067 multiplexer?
There is no speed requirement. So long as rise and fall times are not excessive the sequence of channel switching is of no concern to the mux. (if they are the chip will tend to draw excessive Vdd current due to the time the inputs are at intermediate voltage). 

Normally you'd want to put the 4 or 5 control inputs on a single MCU port so they would all change at once anyway. 

That said, whatever you connect it to may care.