My army was exploring the map when an AI player claimed a territory between them and my empire, effectively cutting them off. I can’t bring them back home without either negotiating open borders (which I have no idea how to do as my options for active diplomacy seem to be limited to trading) or declaring war. There should really be a way to negotiate passage of armies through foreign territory... right now I don’t know what do do with my unit. 

What I figured out was that if you select a space that's either in your territory, unclaimed territory, or territory of an empire you do have Open Borders with your army should be able to get there. They'll still be trespassing but it won't trigger a war. That said, I did have an instance where an army got trapped between an opponent empire's city and some cliffs after I forced surrender, and I wasn't able to free them until I declared war again because they couldn't move through the opposing city xD

Klondike wrote:

What I figured out was that if you select a space that's either in your territory, unclaimed territory, or territory of an empire you do have Open Borders with your army should be able to get there. They'll still be trespassing but it won't trigger a war. 

Didn't seem to work for me. The game would suggest a path (an unusually elaborate one that would involve going via the entire map for some reason), but the army would just sit there the moment they approach a foreign border.