The problem is that whenever you delimit a command with & this command executes in the background and the following command will start immediately with the first command and not after it. Your problem is unrelated to nohup (which means that programs that are still running when the parent shell exits should not be killed but continue execution). For your problem try something like
nohup /bin/bash -s <<< "date; your-script.sh ; date " >& all-output.txt &
This will run your job and output timings in the background and redirect all output to the given file.
BTW, if you are only interested in the runtime, you should do
nohup /bin/bash -s <<< "time your-script.sh " >& all-output.txt &