chsh actually changes the line pertaining to a user in /etc/passwd, though a user can only change his/her own 'line' in /etc/passwd. Hence, if you want to change shell for another user, you need his / her passwd.
If you really want to do it (given the concerns in Lorenzo's post, and possible security concerns) here's how one can do this:
This requires root privileges.
Say you're currently running as "alice" and want to change "bob's" shell without password;
Add to the file:
Cmnd_Alias SHELL = /usr/bin/chsh
Runas_Alias SH = Bob
alice ALL = (SH) NOPASSWD: SHELL
This makes sure 'alice' can run on all hosts as the users in the group SH without a password the group of commands in SHELL.
Probably a bit far fetched to do it this way, but it is possible.
Be sure to read "man sudoers" before changing the sudores file with 'visudo', especially the messages related to security!