How do I change user password on non-AD Windows Server from a Mac?

You could install Samba3 through Macports and then you'll have smbpasswd available again.

1. Install Xcode from Apple - If you download Xcode from the Mac App Store, be sure to use the Xcode preferences to subsequently download the command line tools or use the xcode-select tool to get the BSD command line tools placed in your path. MacPorts needs make, gcc and other tools from Xcode to compile the samba3 code.
2. Install Macports for Lion (or whatever OS X version you are using)
3. Run sudo port -d selfupdate - just to be up-to-date
4. Install Samba3 in Macports: sudo port install samba3
5. Setup smb.conf: sudo cp /opt/local/etc/samba3/smb.conf.sample /opt/local/etc/samba3/smb.conf

You are done, and now you should be able to call smbpasswd -r <serverIPaddress> -U <username> again.

Does the server has Remote Desktop enabled? If so, your users could open an RDP connection to the server and change their password.

You could also use this workaround, as Lion (as you wrote) does not comes with smbpasswd.