This is a harder problem than you may realize. First, it is a permutation problem because you want the final counts for the departments to be the same. Second, there are times where it is not solvable (say, if more than half the employees are in the same department).
If you want to shuffle the departments for employees, here is a method:
with cte as (
select e.*,
row_number() over (order by emp_id) as orig_seqnum,
row_number() over (order by dbms_random.value) as new_seqnum
from employees e
)
select e1.*, e2.dept as new_dept
from cte e1 join
cte e2
on e1.orig_seqnum = e2.new_seqnum;
This does not guarantee that the new department is different from the old one. There are actually ways to make that happen. However, given that most of your departments have only one employee, this might solve your problem.