You might consider a VoIP solution for each location. It may not come with free international calls but it should offer inexpensive rates and unlimited domestic usage for a flat fee. There is also the option of a soft phone. VoIP also enables you to take advantage of advanced features, such as call forwarding and simultaneous ring that can be configured from anywhere on the Internet. Also with VoIP, the service itself is portable, which means that you can take the phone adapter with you, plug it in anywhere that there is an Internet connection and receive your calls that way.
Like you mentioned, there are several options and the best approach will probably be a custom mixture of those solutions.