If /usr/bin/passwd was not a set-UID program, what capabilities would it require for a normal user to still be allowed to change his password?
Impossible unless you want to destroy the security of the system.
If the "passwd" utility can do its job as a normal user, then any user could write their own version to change the password of any other user. (That is, take the source code to the utility, modify it to skip asking for the current password, compile, and run.)
I suppose you could create a "password daemon" that runs as root and listens on a socket in order to service password change requests. Why you would want that instead of a set-uid /usr/bin/passwd is beyond me, though; the security implications are identical.
But no matter what you do, changing the password database can only be allowed for some trusted process. Otherwise anybody can change anybody else's password, which kind of defeats the purpose of a multi-user OS.