On a blank new work computer using Chrome but not logged in, I refuse all cookies but still see myself being tracked, for example by ads targeted to my surf history.
I could think of sophisticated methods, but maybe the simple answer is that refusing cookies doesn't actually do anything?
In the end, you've got two things to work with: Things you can convince the browser to actively identify itself with, and the things you can track regardless.
Cookies are in the first category, but they are not alone. You can get things as simple as presenting an entire site with customized URLs that track a user through querystrings being appended to everything with an identifier. You can track certain caching differences. You can program a website to use local storage and submit a token on every URL click with a fairly simple handler. This isn't even remotely a complete list.
In the second category, you've got IP address, browser versions, various settings... see something like https://www.amiunique.org/ .
In a nutshell, your rich browser experience leaks so much data along so many axes that it is essentially inconceivable that you could ever prevent yourself from being fingerprinted. What you can do is try to detach that fingerprint from a real person, to a certain extent rotate what you can, etc. But in reality you can't be shipping up kilobytes of header information on each web request and expect there isn't something in there that can track you.
https://www.amiunique.org/fingerprint says I'm 100% unique; with all the red lighting up I'm not surprised.