@Diatenshi-Zelda Rox's method works perfectly, it's just a little complicated. Let's walk through a full example so that everyone gets it. (and no, the distribution of hats does not matter, you can still guarantee that at least 9 people survive.).
The hats in order are.
Red, Black, Red, Red, Red, Black, Red, Black, Red, Red. I've purposefully put more red hats than black hats to show that it doesn't have to be an even distribution.
Okay, so this will be our code. If the first person says Red, it will mean that he sees an even number of red hats. If he says black, it will mean he sees an odd number of red hats (it's very important to remember that black corresponds to an amount of Red hats, not black hats). Also none of the people's responses after the first are coded. They are simply stating the color of the hat on their head (which can be derived as I will show)
First person says red because he sees 6 red hats (he got lucky that his hat is also red. Yay 50/50 chances!)
Second person, knowing that the previous person saw an even number of red hats, knows that his hat can't be red (as he also sees an even number of red hats, and his hat being red would've made the previous person see an odd number of red hats). He says black.
Third person. The second person saying black means that the number of red hats hasn't changed (second person still saw an even number of red hats). As he only sees 5 red hats (odd), he knows that his hat must be red for the previous person to see an even number. He says red.
Fourth person. The third person saw an odd number of red hats. How do I know this you ask? Because if you were keeping track the second person saw an even number of red hats, and the third person said his hat was red (implying that his view disagreed with the person behind him). The fourth person sees 4 hats (even) which is different from the person behind him, so he says red.
By now you can obviously see the pattern (unless I made my explanation too convoluted to understand.)
Basically, with my particular code you would say Red every time there's a discrepancy between the set of red hats the person behind you saw and the number of red hats you currently see, as it means that there is one red hat missing from the set (the one you can't see that the other person did). If there's no discrepancy, you say black (as the set of red is still in tact, but there's still a hat on your head).
This method works as long as you make sure that the first person says his color based on the amount of one particular color (red and black both correspond to an amount of red, or they both correspond to an amount of black, but never some combination). Also, past the first person, the responses are no longer in "code."
Hope that helped everyone put this riddle to rest.