If I interpret your question correctly, the answer is that the exponential random variable $\xi$ (density $e^{-x}$) has the property that for two independent copies $\xi_1,\xi_2$ of $\xi$, one has $P(a\xi_1\le b\xi_2)=\int_{y_1\le ry_2}e^{-y_1-y_2}dy_1dy_2=\frac r{1+r}$ with $r=\frac ba$, which is exactly what you wanted (in the first paragraph, at least; the second paragraph problem is completely different from the first paragraph one; I hope you realize that). To convert the uniform variable into the exponential, just take the natural logarithm.
Edit: OK, since you modified the question, I'll modify the answer. The exponential distribution still works but with a twist. Suppose that your weights are $x_1,\dots,x_n$. The probability of the order $1,2,\dots,n$ with your current algorithm is $\prod_{j=1}^n\frac{x_j}{\sum_{k=j}^n x_k}$. Now take $Y_j=x_j^{-1}\xi_j$ and compute the probability that $Y_1<Y_2<\dots<Y_n$. $Y_j$ has density $p_j(t)=x_je^{-x_jt}$. So, the desired probability is $\int_{y_1<y_2<\dots<y_n}x_1x_2\dots x_ne^{-x_1y_1+x_2y_2+x_3y_3+\dots+x_ny_n}dy_1\dots dy_n$. If you now start integrating from $y_n$ down, you'll get the same expression. Thus, you can reduce your simulation to computing logarithms of $n$ uniform on $[0,1]$ random variables, dividing the resulting negative numbers by the weights and sorting.