First, I hope that you've got your credentials set up so the user MUST change them during the first login, so those setting them up cannot know them anymore.
If a remote office has a trusted admin, send that admin an encrypted set of one time use keys/passwords to share with other users, so you can just ask them to use Password #12 for their initial login.
Depending on your threat model (are you worried about nation-state level actors, i.e. are you working with a foreign office in Country 4, which may engage in commercial espionage on behalf of their local competitors of yours), this is actually a classic case where calling someone on a landline is a great solution.
Just calling someone on a landline and telling them the initial login credentials over the phone works very well.
Beyond that, GPG is always a classic way of doing this, as many people answered. I have examples of both public key usage as well as more secure than default symmetric usage in this answer on Superuser.com.
Depending on your regulatory requirements, OTR is a method of encrypting communications, particularly IM's (see Pidgin as an example) that also allows for "shared secret" authentication; you could share an easy to type password on the phone while on IM's to validate the IM session doesn't have a Man in the Middle, or use some aspect of the work they're doing that would be hard for someone else to have ahold of.
If you already have a way to send email that you trust only your recipient and your own network/email admins can access, and you can trust certain other products/companies, then you could use a "secure email" service like Cisco Registered Envelope Service or an alternate.
Particularly for SSH keys or extremely long and difficult passwords, you can do a combination of these; you can encrypt - perhaps using GPG symmetric mode (see link above) - using a secure password, and then deliver that password via the phone or other method, so they can decrypt the actual authentication token/SSH key/certificate/etc.