How do i add towns to provinces (states) list

I have searched and not found a answer to my specific request.

I ship mostly to South Africa customers at present and i need to be able to define towns per province (state) due to a shipping agent that i use that do not work off the postal codes system.
Due to the postal codes that covers such a wide area there are some parts not covered by the courier company so the postal codes would render it pretty useless.

For instance i have a special rate for GT Gauteng Province (state), but not all areas which falls withing the Province are covered or considered as local.
Some other towns in the different Provinces (state) are considered an outlying area and attract additional costs.
I would appreciate help or ideas how to set this up. Perhaps there may already be a similar plugin that i can just reconfigure!