I'm looking for a way to tunnel all network communication from my laptop through another computer. I can control the software on both the laptop and the computer. The connection between them should be encrypted.
Which technique should I use? VPN seems out of the question, as I wouldn't want my laptop to show up on the other computer's LAN.
You can indeed use tun/tap tunneling. The easiest way I know of to do so is using OpenVPN. There are graphical clients for that for most OSs.
If you use 'tap' tunneling, your laptop will show up on the remote LAN, since layer 2 network traffic is also sent through the tunnel. Using 'tun' tunneling however, which occurs at layer 3, only your IP traffic is routed to the remote LAN.
You can use tap/tun ssh tunneling. This way all of your data (as opposed to a specific port in "regular" ssh tunneling) will go through the tunnel. There's an example here: http://www.perturb.org/display/entry/770/
Any VPN will do; just disable "split tunneling". You can get a VPS in a lot of places (e.g., check www.swisscenter.com for a non-US firm that is reliable) and run your VPN server there. OpenVPN works, but so does PPTP and IPSec. Linux VPS can support any of them.
I'm not sure I understand your point about "showing up on the other computer's LAN", but if you, for example, use OpenVPN and then NAT your traffic at the receiver, your traffic will all be marked with the remote computer's source IP address, so without some very advanced heuristics, nobody will know what's really going on. If this doesn't address your concern, could you clarify what you're after?
If you don't want to go the VPN route, you might consider using a remote desktop shell for your needs. If you are on windows you can use RDP, Linux you can use VNC - you can tunnel these securely over SSH or maybe use a built in security mechanism. There are also services like Teamviewer. You can set this up to run your SSH server on port 80, 443, 8080, etc if you roll your own remote desktop.
As for not showing up, VPN/remote desktop/remote shell, no matter what port you run on, you will have a persistent connection which is suspicious. If you are trying to be incognito, I would stick to web services and web apps.
