Generate two queries, one that returns the emp_no's you want to replace with a second column that is numbered sequentially. The other that does the same for the random's. Then in the update, join them based on the numbers.
UPDATE employee
SET e.emp_no=r.rand_val
FROM (query1) e
JOIN (query2) r
ON e.number=r.number
Likely query1 would be something like:
SELECT emp_no,row_number() OVER(ORDER BY emp_no) as number
FROM employee
WHERE employee.emp_no IN (SELECT emp_no FROM employee
GROUP BY emp_no HAVING COUNT(*)>1)
Likely query2 would be something like:
SELECT rand_val,row_number() OVER(ORDER BY NEWID()) as number
FROM random_values
So the whole thing would be:
UPDATE employee
SET e.emp_no=r.rand_val
FROM (
SELECT emp_no,row_number() OVER(ORDER BY emp_no) as number
FROM employee
WHERE employee.emp_no IN (SELECT emp_no FROM employee
GROUP BY emp_no HAVING COUNT(*)>1)) e
JOIN (
SELECT rand_val,row_number() OVER(ORDER BY NEWID()) as number
FROM random_values) r
ON e.number=r.number
It's been a while, you might have to join them back to the employee table as well like this:
UPDATE employee
SET e.emp_no=r.rand_val
FROM employee
JOIN
(
SELECT emp_no,row_number() OVER(ORDER BY emp_no) as number
FROM employee
WHERE employee.emp_no IN (SELECT emp_no FROM employee
GROUP BY emp_no HAVING COUNT(*)>1)) e
ON employee.emp_no=e.emp_no
JOIN (
SELECT rand_val,row_number() OVER(ORDER BY NEWID()) as number
FROM random_values) r
ON e.number=r.number
But you still might have difficulties with the duplicates both getting assigned a new number (or the same random number) unless you can differentiate the emp_no's by some other field. I assume your real employee table has more than just 1 column, and you would need to reference both the emp_no and the unique field in the join to make sure they get assigned different numbers, or eliminate one of the two duplicates in query1.