Thank you Rick and Sticky Bit for you inputs. Sticky Bit's solution would take to long to run. Rick's answer was the closest one and his comments helped me to create the full solution which I'm sharing below.
First, create temporary tables to store random names
DROP TABLE IF EXISTS _RandomFirstNames;
CREATE TABLE _RandomFirstNames (first_name VARCHAR(255));
DROP TABLE IF EXISTS _RandomLastNames;
CREATE TABLE _RandomLastNames (last_name VARCHAR(255));
Then created a procedure to fill those tables with random names to make sure that we have one first name and one last name per each possible user ID.
DELIMITER $$
DROP PROCEDURE IF EXISTS prepare_randon_names$$
CREATE PROCEDURE prepare_randon_names()
BEGIN
SELECT @users := id FROM users ORDER BY id DESC LIMIT 0, 1;
SELECT @mask_ct := COUNT(*) FROM _masked_names._firstnames;
SELECT @loops := @users/@mask_ct;
SELECT @count := 0;
WHILE @count < @loops DO
INSERT INTO _RandomFirstNames (first_name)
SELECT firstname FROM _masked_names._firstnames ORDER BY RAND();
SELECT @count := @count+1;
END WHILE;
SELECT @mask_ct := COUNT(*) FROM _masked_names._lastnames;
SELECT @loops := @users/@mask_ct;
SELECT @count := 0;
WHILE @count < @loops DO
INSERT INTO _RandomLastNames (last_name)
SELECT lastname FROM _masked_names._lastnames ORDER BY RAND();
SELECT @count := @count+1;
END WHILE;
END$$
DELIMITER;
We can now execute it and add incremental IDs to the populated tables
CALL prepare_randon_names();
ALTER TABLE _RandomFirstNames ADD id INT UNSIGNED AUTO_INCREMENT PRIMARY KEY;
ALTER TABLE _RandomLastNames ADD id INT UNSIGNED AUTO_INCREMENT PRIMARY KEY;
Now we can update user table with the random names by joining the two new tables with the random names that we created above
UPDATE users u
left join _RandomFirstNames f on f.id = u.id
left join _RandomLastNames l on l.id = u.id
SET u.first_name = f.first_name,
u.last_name = l.last_name;
And the last step, drop the tables with random names as we no longer need those
DROP TABLE IF EXISTS _RandomFirstNames;
DROP TABLE IF EXISTS _RandomLastNames;
Notes Summary
adding primary key after the tables were populated with random names solved an issue with the index skipping count. For example, in _RandomFirstNames, the ID was increased sequentially until ID 5163 and then skiped to 8192 (by 3,029), then it increased sequentially until 13354 and then skiped again by 3,029 to 16383. _RandomFirstNames was generated based on _masked_names._firstnames, which contained 5163 names.
avoiding count(...) within the while loop increased speed by one second when run against users
table with 250,000 records