NewId is good for this as it acts per row:
$sql = $wpdb->prepare("UPDATE {$wpdb->prefix}my_table_name SET
DisplayOrder = abs(checksum(NewId()) % 10000)
WHERE ListCategoryId = %d
", $ListCategoryId);
if (current_user_can('administrator'))
$wpdb->show_errors();
$wpdb->query($sql);
//abs(checksum(NewId()) % 10000) <<<Generates a random number between 0 and 9999
Feel free to comment if you can add help to this page or point out issues and solutions you have found. I do not provide support on this site, if you need help with a problem head over to stack overflow.