I'm not aware of any "permute column cells subject to constraints" dialogue in Microsoft Excel. As indicated by Burgi, you can write a script to make Execel do exactly what you want.
If you have never written a script or done any programming before, set aside at least a day. It's a huge investment of time but will pay off in the long run. Your new skills will enable you to solve other problems in Excel more efficiently as well.
Start with writing a script that checks whether cell B1 conflicts with cell A1. Then write a script that swaps B1 with another cell from B2 to B5. Then make the swap subject to the constraint that the new contents for B1 resolves a previous conflict with A1. If you want it more random, don't just pick the first cell that fits but make a random pick from all suitable cells. One way of doing this is to first count how many cells fit the constraints, obtain a random integer i in that range and then scan column B again this time stopping at the i-th cell that is suitable for swapping. Then write a loop that iterates over all cells of column B and modify your previous code such that it works not just for B1 but for any other cell in column B. Only swap with cells further down. Swapping with cells that have already been checked would mean that you have to check those cells again and you might end up running in circles, never finding a solution even if a solution exists. Once you mastered this, you will find it easy to extend your script to handle column C as well. Finally, learn how to report error conditions, for example that no suitable cell is available. (6 Es in your example would be a suitable test case.)