I have added a new mode to the tool for generating setups for handicap games:
(it’s similar to the tool @runarberg shared but with a bit fewer options)
I think random handicap is a really nice format, and I’m going to try to popularize it at my local club!
The handicap positions generated by my tool are not checked by KataGo in any way, they are just purely random placements, optionally with some restrictions on the spacing. You may think that this would make it so that the strength of the opening is very luck dependent, but there isn’t actually that much variance. Here is a histogram representing 8000 random boards generated with spacing=1:
Each color represents a different number of handicap stones, from 2 up to 9. As you can see, there is barely any overlap between the distributions: The “luckiest” placement of 2 stones is still worse than the “unluckiest” placement of 3 stones. (For higher handicap we see a little bit of overlap, but the unluckiest placement of 9 stones is still better than the average placement of 8 stones)
As expected, randomly placed stones are not quite as valuable as starpoints. The solid lines represent the mean of each distribution (a representative close to the mean is shown for 2, 5 and 8 stones), and the dashed lines show the standard placements for comparison.
For 2 stones, the average number of points you “lose” by random placement compared to standard placement is less than 3 points. For 9 randomly placed stones, the average value is roughly the same as for 8 standard handicap stones.
Based on this, I suggest calculating the “random handicap” as “normal handicap + 1”: If you are 3 stones stronger than your opponent, you can give them 4 randomly placed stones as handicap.
According to KataGo, this favors black (who on average gets a bigger point lead than they would with normal handicap), but in human terms it is probably to the stronger player’s advantage that the initial position is unfamiliar. So my guess is that the “normal handicap + 1” rule is relatively fair in practice!
Let me know how it goes if you try it out 
Try the new mode here: random-go.antontobi.com