If you flip a coin it will randomly be heads or tails. But, if you flip the coin 1000 times you can predict that about 500 will be heads and 500 will be tails which is no longer random. So, does randomness exist? Or does it only exist with a small sample size?

As long as the coin is truly "fair," then indeed this is a random process. It doesn't matter what happens on the first N tosses, you have no way of knowing whether the N+1st toss will be heads or tails - so it's random. The number of possible sequences in 1000 coin flips is 2^1000, which is a truly stupefying number of possibilities (much much larger than a googol), and each one of those squences is equally likely to occur. The fact that getting 500 heads and 500 tails is much more likely than all heads is because there are more sequences that have 500 heads and 500 tails in them (about 10^29 such sequences) than there are sequences with 100 heads and 0 tails (there's just one of those).

All this assumes that the coin is truly "fair." You can get into a long discussion about whether there are actually any physical processes in nature that are truly random, but that's another topic.