But would that even be the end of it? With Wifi off the phone is still broadcasting on cellular channels. Could a device be built that listened to those signals and uniquely identify them?

Also in terms of cost, there's a difference between tracking which imposes a marginal human cost of production versus tracking which can be fully automated by machine, even if there is still a per-machine cost.

A relevant example is the Supreme Court ruling on needing a warrant for using a GPS tracker on a car versus just tailing them.

There are several applications for OSX and various *nix distros that run at boot and randomize MACs. SpoofMac is probably the most well known: https://github.com/feross/SpoofMAC

First: You do not want a MAC collision. I have worked with hardware that sometimes picked a non-unique MAC and your life gets really weird and sucks away a lot of debugging time to find out why impossible things are happening.

Continuing – It made ethernet easy to implement. They could have added some complicated address negotiation protocol and then handled address collisions when partitioned networks healed, but it was "olden times" and something that complicated would not have gained traction.

Fast forward to Wi-Fi. The reason you have Wi-Fi instead of any number of other wireless ideas that died is because it looks like ethernet so people didn't have to think much about it, so you inherit that baggage.

If you really want to change your MAC address then you will want to make sure you aren't going to collide with anyone else. The odds are tiny, but it would be rude to ruin their day. Fortunately, there is a locally administered range of MAC addresses. If your first octet's last digit is 2, 6, a, or e then you are a locally administered unicast address. Assuming your network segment doesn't have an administrator actively handing out local addresses, drop 56 random bits in the remaining octets, cross your fingers, and bring up your network stacks.