Is it possible to change the admin user/password remotely on a router without logging in? If yes, how so?
This depends on which router you try it on. You can't expect an exploit or security hole to work on all routers. So by exploiting a design flaw or something similar you could certainly change a router's password.
However, most vendors would try to patch something like this asap.
For example, searching osvdb.org for ZyXEL produces a long list of exploits. Check it out here