OK, here's no voodoo, no blind-trying and (I hope) well explained solution to this (sorry for the rage, I tried googling for solution almost for a whole day to no avail).
First, let's read about ways adb communicates with the device:
https://android.googlesource.com/platform/system/core/+/master/adb/protocol.txt
Short story: host adb establishes server on 5037, connects to adbd on the device via tcp port 5555 (default).
That means - to work, your adb's got to have a clear road to your local 5037 and remote 5555.
You can setup adbd on the device (using device terminal) to listen without establishing USB connection first, if you cannot or do not want to use USB:
setprop service.adb.tcp.port 5555
stop adbd
start adbd
Check with netstat -plant | grep adbd if adbd is listening on port 5555 (or any other you've chosen).
Now fire up Wireshark with capture filter port 5555. Execute this command on your host: adb connect device_ip:5555 (replace 5555 if you're using non-standard port).
According to the document above, you should see CNXN commands from both directions! If your remote end doesn't reply, adb devices will say your device is offline! And it's a game over. adb devices doesn't do any network exchange, it just shows you the result of the adb connect command.
My problem was - I've been running Android inside a Virtualbox with NAT networking and forwarded 5555 port. Also, I had an emulator running on port 5554. It didn't occupy 5555, but somehow, these two interfered and disrupted Virtualbox's connection at the lower level, as I had lots of weird duplicate ACKs and RSTs flying all over the interface. A solution for this problem was to pick a different port.
Please tell me if I'm wrong, but I didn't see anyone proposing this before. Neither explaining how and why it should work.