You cannot easily 'enter a password' with ssh, it is built to bypass most attempts at that.
The passwd command is also that way. You will need to bypass those problems which involves some advanced techniques.
What you will have to do is one of these:
1. If you are root or an admin, ssh to the remote box and do password changes one by one manually
2. install the "expect" application and create an expect script to answer all the prompts. You outlawed that already.
3. write a pty emulator in C that can become the sessions leader/terminal owner.
see:
Solaris Systems Programming
download: source code The code you want is called pty.c It is meant for Solaris, but with minor changes it will work on linux.
It is basically like expect in that it allows batch interaction with passwords embedded.
Which BTW is a terrible idea.
Since you have a few routers, this post sat unaswered for a while, maybe you could have completed the task manually. If you want a longterm solution consider #2 or #3.