Eu começaria com algo assim. Um monte deles pode ser combinado, mas eu divido para que você possa ver o que estou fazendo.
Para obter números aleatórios, você pode usar rand(). Obtenha um para a data, hora, minuto e segundo
$randomDate = rand(1,31);
$randomHour = rand(1,24);
$randomMinute = rand(0,59);
$randomSecond = rand(0,59);
Você vai querer zeros à esquerda (03 em vez de 3) para que você possa usar str_pad para adicioná-los, se necessário
$randomDate = str_pad($randomDate, 2, '0',STR_PAD_LEFT);
//The '2' is how many characters you want total
//The '0' is what will be added to the left if the value is short a character
Faça o mesmo com todos os seus outros valores aleatórios. Só porque eu gosto de consultas organizadas, você deve criar suas strings de atualização final em seguida.
$newDate = '2008-09-'.$randomDate;
$newTime = $randomHour.':'.$randomMinute.':'.$randomSecond;
Agora, não sei como você está determinando quais linhas deseja atualizar, então deixarei isso para você. Por exemplo, mostrarei uma consulta se você quiser fazer isso com Primary_id 3:
$x = mysql_query("UPDATE yourTable SET Begin_Date=\"$newDate\", Timestamp=\"$newTime\" WHERE Primary_id = 3");
