sort -u input.txt |\
    perl -pe '$r = substr(rand(), 2); $_ = "$r\t$_"' |\
    sort -n | cut -f 2- > output.txt
[download]

sort is optimized to work well with really large files. You may want to use the -S and -T parameters on sort.