The legend you want is actually redundant for your chart because the departments are shown on the X-axis so the quick answer might be don't show the legend. However, there is a way to get the result you are after - the departments in the legend with their colour.
You're using the wrong chart type for what you are trying to do. What you are graphing is, say, sales by department. In a simple column graph this is one dimensional, so the legend is just "Sales" and the X-axis shows the departments, but you want the departments to have different colours. Now, as you found out you can override the column fill colour but the legend is still only displaying the one dimension for the chart which is sales.
What you what the legend to display is the departments with their colours. Use a Stacked Column chart type: for the Sum Values have the sales field, for the Category Groups have the department name and for the Series Groups have the department name. This will then stack the sales values for each department within each department and because each department only has sales figures for itself and not for the other departments the other departments will not be shown (only that department's figures are shown) and you get the result you are after.
The legend will now show each department with the appropriate colour. You can continue to use your colouring expression for the fill and this will be reflected in the legend.