Windows Password Sync without using Active Directory

[An executive made a decision that we will never use Active Directory in the cloud. So I'm looking to work around that decision.]

Then I'm afraid you're going to have a bad time. What you're asking for isn't going to be as easy as AD. Because an executive made a poor decision, you're not unable to use the correct, first-party, purpose-built tool for the job.

One solution that comes to mind is using PowerShell DSC and integrate it with an existing CM platform that you might already be using in the cloud (Chef, Puppet, Ansible, etc).

Create a VPN between your cloud network and your on-premise network, and then use your on-premise AD

Novell Identity Manager is also an option, though AD really is better suited for the task. Novell's solution requires an eDirectory Vault and the Novell Client on each system. Check this link if you're curious IDM Implementing Password Synchronization. IDM allows you to build drivers which synchronize passwords between eDirectory and Active Directory. If you propose this solution, you're exec will likely acquiesce to using AD as Novell has increased cost and headaches.