Of course technically you can often reprogram your MAC address with a lower-level utility.
It wouldn't necessarily be *easy* to trace, but you'd be unwise to assume that just because you were using an anonymous WiFi that you weren't leaving some fingerprints...
If you have Windows Update, anti-virus software, or all manner of newer applications they phone home surprisingly frequently, and if nothing else, their records could be used to prove that your computer was connected to the "anonymous" WiFi network at or near the time of your dubious download or hacking session.
If you had a mobile phone about your person at the time, then forensic records from the telco could indicate that you were within a few 100 metres (or less) of the WiFi shop at the time of "the incident".
The shop, high-street, or mall will probably have CCTV which will show you were there.
A few hours ago, I installed a printer for someone. During the install, the printer driver asked permission to (during the life of the printer) send back to the manufacturer counts of pages printed, ink-levels remaining, and various other statistics.
Is that any of their business? It's more spying, and more digital fingerprints.
Many colour laser printers overlay all colour prints with a matrix of very fine almost invisible yellow dots, which code the serial number of the machine that made the print and the date and time at which the print was made. If you illuminate such a page using a blue LED light and look very closely, you can see the dots. Allegedly this coding is to help enable the tracing of any forged documents or currencies etc which are printed. But it's more spying.
Moral: never assume anything you do digitally is untraceable these days.