Every network card has unique MAC address that's used for network communication before IP-based connection is estabilished. That's why using your everyday PC isn't a good idea. That's also why using a new PC isn't a good idea, as its MAC is unique too.
MAC itself indicates network card's manufacturer that you could possibly contact. Then you can ask them for some more info and this way possibly even track down where that network card/laptop with that network card was sold to you. If they have surveillance cameras, then they know you.
Using a virtual machine isn't a solution, as entire network communication will still be routed through host machine via NAT.
Possible solution: mask MAC address before connecting.
Windows has a bunch of services that use your network without your knowledge, especially one that checks if your connection works. So basically it will try to say "hello" to Microsoft everytime you connect to the Internet. There's also Windows Update, time synchronization service etc. etc.
Possible solution: use custom Linux distro, those are easier to keep in check as you can compile those yourself, checking every single line of code. (it's paranoid, but we both know your question is too ;)
Many other apps have autoupdaters running in the background - every single one will try to contact some remote server, telling it something about your connection.
Possible solution: use a firewall with whitelist. Make sure it doesn't call somewhere itself.
Your browser will be quite unique, you can check it here. The one I'm using now is unique among 2,987,405 tested so far. So was Chrome on my Android smartphone.
I can't think of any reliable solution for this problem, because there's no such thing as an "average browser".
You're not anonymous when using public Wi-Fi. All your communicaton can be easily captured and intercepted with a $100 device and there's no reliable way to check if your connection is safe. On the other hand, encrypted Wi-Fis are usually not anonymous by design - you need to acquire login credentials or connection password, and this limits the number of potential suspects greatly.
Possible solution: I can't think of any. (comments are welcome)
Your IP discloses your Internet provider, and thus your approximate location. Possible solution: anonymous proxy (if you trust those) or Tor.
Your phone. Well, that's a long story. You never know if it's not tracking you right now. You can use Replicant or something like that, but it's just software and you can't be sure what's in your hardware.
If your phone can get it's location based on GSM towers in radius, then they can identify you too. That's just for starter.
The Google Car doesn't only take photos for Google Maps, it also saves names of Wi-Fis in radius. When you run Google Maps in your mobile, it will first try to get approximate location using GSM and then by names of networks your phone can connect to. Basically, it probably can approximate your location to a circle with diameter of 30 meters. But I guess your phone has GPS too, so...
Turning the phone off isn't an option, as you still don't know if it's completely off. SIM card isn't required for it to operate. Battery is, but not all phones have removable battery.