How to connect ADB over 3G/4G? I keep seeing warning signs about enabling ADB over Network when you aren't connected to a WiFi network, but what if I want to connect ADB over 3G/4G ? 

Whenever I try to do it with any of the conventional WiFi methods, it returns an invalid IP to connect to.  I even tried getting the IP with # ip addr show - but that didn't work, either. 

Any ideas on how to do this? 

Yeah, it isn't safe. But how does such a vulnerability get leveraged when the IP address is likely to change?
Opening ADB on an unsecured connection is a major security risk.  On an unrooted phone, it gives access to your entire filesystem.  On a rooted phone, it gives access to your entire filesystem with write permissions.  The connection isn't encrypted and there is no password or key exchange to access ADB.  It's just a bad idea.  Beyond that, your carrier may not even allow traffic over 5555 (the standard ADB port), they may be proxying your traffic, or there may be other complicating factors.

Also, setting up SSH shouldn't be difficult.  I use SSHDroid all the time.  I can get a secure shell from any WiFi connection, and it works great for wireless file transfer.  You could set up a task to turn on SSHDroid whenever the device connects to WiFi and another to send you the IP.  Technically, you can even run it without WiFi, but I generally wouldn't recommend it, as it's still open to vulnerabilities, which would lead to problems similar to leaving ADB open (although somewhat less likely since SSH is designed to be secure).

Finally, there are a number of apps that are built specifically for locating your phone.  Motorola includes this feature with Motoblur, which can also wipe your phone remotely.  There are other free and paid alternatives that can do this as well.  If your phone is actually stolen, these are going to be much better than any back door you open for yourself.