MyLocalMachine ----||----> MiddleMachine --(netcat)--> AnotherMachine
 ('localhost')  (firewall)   ('1.1.1.1')                 ('2.2.2.2')

cli = paramiko.SSHClient()
cli.set_missing_host_key_policy(paramiko.AutoAddPolicy())
proxy = paramiko.ProxyCommand('ssh user@1.1.1.1 nc 2.2.2.2 22')
cli.connect(hostname='2.2.2.2', username='user', password='pass', sock=proxy)

cli1 = paramiko.SSHConnection()
cli1.set_missing_host_key_policy(paramiko.AutoAddPolicy())
cli1.connect(hostname='1.1.1.1', username='user', password='pass')
shell = cli1.invoke_shell()
shell.send('nc 2.2.2.2 22')
shell.recv(1000) # In case the output of the above is somehow tripping up cli2
cli2 = parmiko.SSHConnection()
cli2.set_missing_host_key_policy(paramiko.AutoAddPolicy())
cli2.connect(hostname='2.2.2.2', username='user', password='pass', sock=shell)

/usr/lib/python3.5/site-packages/paramiko/packet.py in read_message(self)
    399         leftover = header[4:]
    400         if (packet_size - len(leftover)) % self.__block_size_in != 0:
--> 401             raise SSHException('Invalid packet blocking')
    402         buf = self.read_all(packet_size + self.__mac_size_in - len(leftover))
    403         packet = buf[:packet_size - len(leftover)]

"ssh -f user@anothermachine -L 2000:localhost:22 -N"

paramiko.connect(middlemachine, 2000)

import paramiko


class ParaProxy(paramiko.util.ClosingContextManager):
    def __init__(self, stdin, stdout, stderr):
        self.stdin = stdin
        self.stdout = stdout
        self.stderr = stderr

    def send(self, content):
        try:
            self.stdin.write(content)
        except IOError as exc:
            print('IOError exception.')
            return
        return len(content)

    def recv(self, size):
        buffer = b''
        while len(buffer) < size:
            buffer += self.stdout.read(size - len(buffer))
        return buffer

    def close(self):
        self.stdin.close()
        self.stdout.close()
        self.stderr.close()

    def settimeout(self, timeout):
        print('Attempt to set timeout to {} - ignoring.'.format(timeout))

# Connecting to MiddleMachine and executing netcat
mid_cli = paramiko.SSHClient()
mid_cli.set_missing_host_key_policy(paramiko.AutoAddPolicy())
mid_cli.connect(hostname='1.1.1.1', username='user', password='pass')
io_tupple = mid_cli.exec_command('nc 2.2.2.2 22')

# Instantiate the class
proxy = ParaProxy(*io_tupple)

# Connecting to AnotherMachine and executing... anything...
end_cli = paramiko.SSHClient()
end_cli.set_missing_host_key_policy(paramiko.AutoAddPolicy())
end_cli.connect(hostname='2.2.2.2', username='user', password='pass', sock=proxy)
end_cli.exec_command('echo THANK GOD FINALLY')