Для начала попробуем просто сгенерировать любую дату:
SELECT FROM_UNIXTIME(RAND() * 2147483647) AS `rand`
где 2147483647 это самый большой таймштамп равный "2038-01-18 19:14:07"
Теперь следующий шаг, сгенерируем случайную дату для (например) 2011 года
SELECT FROM_UNIXTIME(RAND() * (1325275200 - 1293825600) + 1293825600) AS `date_field`
Где 1325275200 = "2011-01-01", а 1293825600 = "2011-12-31" т.е. общий вид формулы:
RAND() * (end - start) + start
Для большей читаемости можно написать
(end - start) * RAND() + start
Для перевода из DATETIME в TIMESTAMP можно воспользоваться функцией UNIX_TIMESTAMP:
UPDATE `tbl_name` SET `date_field` = FROM_UNIXTIME(
RAND( ) * ( UNIX_TIMESTAMP( '2011-12-31' ) - UNIX_TIMESTAMP( '2011-01-01' ) ) + UNIX_TIMESTAMP( '2011-01-01' )
)