>>
You can't tell from a single test if a stretch of 500 heads followed by 500 tails is non-random: you'd have to permute or at the very least replicate
<<

The 500H,500T sequence would be extremely good evidence of a non-random generation. By my reckoning, in any one trial of 500 tosses, you have about 1 chance in 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 (== 10**50) of throwing all heads or all tails.

The odds of throwing the sequence are therefore about 1 in 10**100 - a googol. If that is not a good enough result, how would replicating the result help? You just change the odds to 1 in 10**200.