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