Generación de tiempo aleatorio distinto en el intervalo fijo

El problema OP tenía mientras usaba solo rand() se debe a su evaluación una vez por consulta .

De la documentación :

El enfoque que se describe a continuación elimina la optimización y suprime este comportamiento, por lo que rand() se evalúa una vez por fila :

dateadd( second
       , rand(cast(newid() as varbinary)) * 43200
       , cast('08:00:00' as time) )

• newid() genera un valor único de tipo uniqueidentifier ;
• el valor se convierte con cast para ser usado como semilla en rand([seed]) función para generar un float pseudo-aleatorio valor de 0 a 1 y como semilla siempre es único, el valor devuelto también es único.

SQLFiddle