This is really the correct way to accomplish what this project is trying to do. No central proxy server that you need to trust and can be trivially done with the commands you already have installed.
I would honestly highly recommend against using Teleconsole for those reasons.
No it is not. Connecting two machines behind two different NAT'ed networks requires a proxy of some kind, and there's nothing you already "have installed" that would help you.
Teleconsole is an instant VPN+SSH in one command and it would be wise to educate yourself on what it does (reading just the 1st sentence of the blog post would be a good start) before recommending anything.
I would honestly highly recommend against using Teleconsole for those reasons.