wpa_supplicant already does this (Score 1)

Screw NetworkManager, its broken anyways and wpa_supplicant can already do everything one might want there:

Add 'mac_addr=1' and 'preassoc_mac_addr=1' to your /etc/wpa_supplicant.conf. Then your MAC-address will be randomized during the Scanning/Preassociation phase and afterwards.

For networks that need a static MAC address for filtering, add 'mac_addr=0' in the appropriate 'network' section. You also want to make sure you are using 'dhcpcd' instead of 'dhclient' (alias isc-dhcp-client). The latter can't deal with changing MAC addresses, it seems.