O problema é que sempre que você delimitar um comando com & , este comando será executado em segundo plano e o seguinte comando será iniciado imediatamente com o primeiro comando e não após isto. Seu problema não está relacionado a nohup (o que significa que os programas que ainda estão em execução quando o shell pai sai não devem ser eliminados, mas continuar a execução).
Para o seu problema, tente algo como
nohup /bin/bash -s <<< "date; your-script.sh ; date " >& all-output.txt &
Isso executará o seu trabalho e os timings de saída em segundo plano e redirecionará toda a saída para o arquivo fornecido.
BTW, se você está interessado apenas no tempo de execução, você deve fazer
nohup /bin/bash -s <<< "time your-script.sh " >& all-output.txt &