I can say for certain that I worked for a company that wasn't Google and employed plenty of ways to track people that didn't involve cookies.

We used it mostly to try and track malicious users (banned users, etc.) but it's still tracking nonetheless. It was reasonably effective.

I'm sure a company of Google's size and sophistication has many more advanced methods than we did.