When it comes to redundancy, basically we use either HA-SKU Controller with each WLC or N+1 HA SKU Controller [can be HA SKU (AIR-CT2504-HA-K9 - supports 75 AP) or normal one with minimum of 5 AP License - AIR-CT2504-5-K9 can be converted to HA SKU secondary WLC].
In your case you have got a new WLC, you need to make sure that you have sufficient license available (I think you already have license) in your new WLC to support all the AP's which are currently with 4 different locations, if WLC's fails.
Configure your new WLC as it is like all other WLC and give WLC name and IP info to High availability tab of AP.
You can infact also use your new wlc as HA SKU if it has atleast 5 AP License to support max hardware capacity, meaning if it is 2504 normal controller with minimum 5 AP License and if you are converting it to HA SKU then it can handle 75 AP.
* The best practice would be to buy AIR-CT2504-HA-K9 (HA-SKU UDI - 0 License) WLC and configure this for N+1 HA for all the 4 WLC if you cannot keep HA SKU WLC with each one.
To configure N+1 HA, use this command..
Primary WLC : config advanced backup-controller primary backup_controller_name backup_controller_IP_address
To configure normal controller to HA-SKU secondary WLC, use this command..
config redundancy unit secondary