How to show a notification when you go online/offline?
I have a home-grown script that uses a rather inelegant polling mechanism to identify open network connections, and takes action based on what it finds. In short, it turns my wifi on or off depending on if it's plugged into a LAN. This to avoid connecting our corporate LAN with our visitors wifi. It uses ifconfig to obtain this data. 

It's fairly easy to identify which interface routes your public internet, using netstat -r I think. 

To the determine if the connected internet is actually working, I would probably using ping -c 1 www.google.com or something and see which code ping exits with to determine if it's alive. 

All very "sticks and strings" I'm afraid. But you did say you're open to that!