I think the root of my issues is no clear understanding of how authentication works along with ProxyCommand. In my setup I have public key auth with host that I use in ProxyCommand to run nc. And the destination host needs password auth. So when I supply username/password - which host does it apply to ? One that is serving as a relay and running nc or the final destination ?

Here is relevant part of my code. May be I need properly destroy $ssh before opening new connection too. To not stumble upon remains of the previous failed public key attempt.

while ( GO OVER ALL HOSTS I HAVE ) {

        // FIGURE OUT IF CAN BE REACHED DIRECT

        my $ssh;

        my @pw_opts = (
                -o      => "CheckHostIP no",
                -o      => "ConnectionAttempts 1",
                -o      => "ForwardAgent yes",
                -o      => "HashKnownHosts no",
                -o      => "StrictHostKeyChecking=no",
                -o      => "VerifyHostKeyDNS no",
                -o      => "UserKnownHostsFile /dev/null",
                -o      => "ConnectTimeout 5",
                -o      => "HostbasedAuthentication no",
                -o      => "ChallengeResponseAuthentication no",
                -o      => "RhostsRSAAuthentication no",
                -o      => "GSSAPIAuthentication no",
        );

        my @pubkey_opts = @pw_opts;

        push @pubkey_opts, ( -o => "PasswordAuthentication no");
        push @pubkey_opts, ( -o => "PubkeyAuthentication yes");
        push @pubkey_opts, ( -o => "PreferredAuthentications publickey
+");

        push @pw_opts, ( -o => "PreferredAuthentications=password");
        push @pw_opts, ( -o => "NumberOfPasswordPrompts=1");


        if( NOT REACHABLE DIRECT ) {
                push @pw_opts, (-o => 'ProxyCommand=ssh root@'.$sshgw.
+' nc %h 22');
                push @pubkey_opts, (-o => 'ProxyCommand=ssh root@'.$ss
+hgw.' nc %h 22');
        }

        $ssh = Net::OpenSSH->new(
                $user.'@'.$host,
                master_opts             => \@pubkey_opts,
                master_stdout_discard   => 1,
                master_stderr_discard   => 1,
        );

        if($ssh->error) {

                print "SSH key auth didn't work for $host, will try pa
+sswords...\n";

                foreach my $pass (@passwords) {

                        $ssh = Net::OpenSSH->new(
                                $user.'@'.$host,
                                password                => $pass,
                                master_opts             => \@pw_opts,
                                kill_ssh_on_timeout     => 1,
                        #       master_stdout_discard   => 1,
                        #       master_stderr_discard   => 1,
                        );

                        if(!$ssh->error) {
                                print "Authenticated with password to 
+$host\n" if($debug);
                                last;
                        } else {
                                print "SSH returned : ".$ssh->error."\
+n" if($debug);
                        }
                }

                if($ssh->error) {
                        print "Can not login into $host : ".$ssh->erro
+r."\n";
                        next;
                }

        } else {
                print "SSH key accepted at $host\n";
        }
}
[download]

# call args: ['ssh','-o','CheckHostIP no','-o','ConnectionAttempts 2',
+'-o','ForwardAgent yes','-o','HashKnownHosts no','-o','StrictHostKeyC
+hecking=no','-o','VerifyHostKeyDNS no','-o','UserKnownHostsFile /dev/
+null','-o','ConnectTimeout 15','-o','HostbasedAuthentication no','-o'
+,'ChallengeResponseAuthentication no','-o','RhostsRSAAuthentication n
+o','-o','GSSAPIAuthentication no','-vvv','-o','PasswordAuthentication
+ yes','-o','PubkeyAuthentication yes','-o','PreferredAuthentications=
+publickey,password','-o','NumberOfPasswordPrompts=2','-o','ProxyComma
+nd=ssh root@192.168.1.1 nc %h 22','-o','ServerAliveInterval=30','-x2M
+N','-o','NumberOfPasswordPrompts=1','-o','PreferredAuthentications=ke
+yboard-interactive,password','-S','/root/.libnet-openssh-perl/root-XX
+XXX','-l','root','10.20.30.40','--']
[download]

# call args: ['ssh','-o','CheckHostIP no','-o','HashKnownHosts no','-o
+','StrictHostKeyChecking no','-o','VerifyHostKeyDNS no','-o','UserKno
+wnHostsFile /dev/null','-o','HostbasedAuthentication no','-o','Challe
+ngeResponseAuthentication no','-o','RhostsRSAAuthentication no','-o',
+'GSSAPIAuthentication no','-o','ProxyCommand=ssh -o "PasswordAuthenti
+cation no" -o "GSSAPIAuthentication no" -vvv -k root@192.168.1.1 nc %
+h 22','-o','PasswordAuthentication yes','-o','PubkeyAuthentication ye
+s','-o','ServerAliveInterval=30','-x2MN','-o','NumberOfPasswordPrompt
+s=1','-o','PreferredAuthentications=publickey,keyboard-interactive,pa
+ssword','-S','/root/.libnet-openssh-perl/root-10.20.30.40-16309-99228
+','-l','root','10.20.30.40','--']
[download]

debug1: Authentications that can continue: publickey,gssapi-with-mic,p
+assword
debug3: start over, passed a different list publickey,gssapi-with-mic,
+password
debug3: preferred publickey,keyboard-interactive
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Trying private key: /root/.ssh/id_rsa
debug3: no such identity: /root/.ssh/id_rsa
debug1: Trying private key: /root/.ssh/id_dsa
debug3: no such identity: /root/.ssh/id_dsa
debug2: we did not send a packet, disable method
debug1: No more authentication methods to try.
Permission denied (publickey,gssapi-with-mic,password).
[download]

ssh -o "CheckHostIP no" -o "HashKnownHosts no" -o "StrictHostKeyChecki
+ng no" -o "VerifyHostKeyDNS no" -o "UserKnownHostsFile /dev/null" -o 
+"PasswordAuthentication yes" -o "PubkeyAuthentication yes" -o "ProxyC
+ommand=ssh -vvv root@192.168.1.1 nc %h 22" -o "ServerAliveInterval=30
+" -x2MN -o "NumberOfPasswordPrompts=1" -o "PreferredAuthentications=p
+ublickey,keyboard-interactive,password" -S /tmp/zzz -l root 10.20.30.
+40
[download]

debug3: remaining preferred: publickey,keyboard-interactive,password
debug3: authmethod_lookup publickey
debug3: remaining preferred: keyboard-interactive,password
debug3: authmethod_is_enabled publickey
debug1: Next authentication method: publickey
debug1: Offering DSA public key: /HOME/MY_KEY.DSA
debug3: send_pubkey_test
debug2: we sent a publickey packet, wait for reply
debug1: Server accepts key: pkalg ssh-dss blen 432
[download]

That happens because requesting password authentication disables the authentication agent.

The solution is just to not ask for password authentication in the gateway:

my $ssh_gw = Net::OpenSSH->new($gw); # no password given, authenticate
                                     # using public key on the gateway

my $proxy_command = $ssh_gw->make_remote_command('nc %h %p');

my $ssh = Net::OpenSSH->new($host,
                            password => $password, # request password 
+authentication
                            master_opts => [-o => "ProxyCommand=$proxy
+_command"]);
[download]

That was it ! I was pretty sure that ProxyCommand goes by itself, is non-interactive and uses only public key. And whatever is requested in OpenSSH->new() applies to the destination host. Thank you for help