I was thining about what you are attempting to do, and there is one falw I came up with. The first random url, will always have a higher weight than all the other urls. Thus it would always be chosen for redirection.
Now a slight addition to your theory could be to select say 5 random urls and then chose the highest weighted from the random 5. The random more urls you chose the less random the redirection will be based on the weight, chose a good number for the total urls you have. You will proabaly have to experiment with this.
Obvioulsy what ever theory you go with, you will need to "UPDATE", the mysql table to increase the weight of the chosen URL.
That should give you a little to think about...
Let me know if there is anything else I can do..
PHPdev