Expect is usually the best tool to automate anything asking for a password at the tty. So what are the reasons you have to avoid it?

Net::OpenSSH::Parallel is a module that can be used to run commands in several hosts in parallel and it can be easily integrated with Expect to automate the sudo authentication steps. Look for sudo on the module documentation for an example.

Also, if the version of sudo installed on the remote machines is recent enough you may be able to pass the password directly through stdin. That is covered in Net::OpenSSH documentation.