You can easily change the MAC address reported by most network stacks, and however that address is not routed, per se, past your network gateway.
What could give you off might be:
- the software on the device. Browsers and the like all have a specific signature, and the Electronic Frontier Foundation even has an "estimating" gadget to tell you how unique your "fingerprint" is.
- hidden software on your device (i.e. spyware).
- your navigation pattern. Most people are not aware of this, but they usually tend to adhere to a broad navigational routine. This might be enough to restrict a search using Big Data and a powerful access to an area's networking infrastructure (i.e. you need to be the government or a large ISP).
- the network itself might not be trustworthy. It might be easy for a large equipment manufacturer to embed backdoors and surveillance code, and even implement an "internet over the internet" using, for example, damaged IP packets that would be dropped by normal routers, but have significance for devices of a specific manufacturer. This of course would require a large equipment manufacturer to be essentially the property and toy boy of a large Nation-state. Then, seeing the significant strategic value of such an operation, the manufacturer might be directly or indirectly subsidized by the State (e.g. with large tax cuts on its suppliers, so that they can afford lower prices), driving the prices down and letting the compromised equipment flood the market, until most cheap devices are running it, or running on it, or communicating through it.
So:
Basically, how can the device be made to look like a completely new or random device with no way to trace it back whatsoever?
For large values of "whatsoever", you need a new device. One that has never been used for any other purpose, and whose usage is itself randomized using some reliable technique (dices?).
Otherwise, you can run a virtual machine inside a reliable hardware, and reassign new information - MAC, hard disk serial number, DMI etc. - every time. Maybe, by comparing a new, virgin VM and a new, virgin VM with changed information, you can come up with the offsets where that information resides, and at that point you can script a complete machine regeneration using a blank template and random values poked at those offsets; creating a "new" machine then becomes just the matter of a few clicks.