Could this be done with an extension?
As far as I am aware, no extension currently offers the option of a random user agent, but many (including the one linked) allows user supplied use agents, and there is no reason you could not make one support random user agents.