Boa tarde.
Então, esses usuários não possuem acesso interativo com o servidor? Ou seja, não possuem qualquer tipo de acesso a shell, terminal ou X11.
Se possuírem uma shell (mesmo que não a use), pode emular uma sessão telnet ou ssh via php e enviar os comandos para a troca de senha.
Evite soluções que precisem forçar permissões de root, como o uso de sudo ou similar (além dos que já são fornecidos pelo sistema).
Caso os usuários realmente não precisem de uma shell, como em um servidor de email, pode-se migrar a base de usuários para um mais fácil de lidar externamente, como LDAP, SQL, etc.
Usuários do samba podem trocar a senha via o windows ou outra ferramenta SMB/CIFS. A senha do samba pode ser sincronizado com o do passwd/shadow.