Learning a perceptron from stream data
I think you're confusing yourself by worrying about a worst case that likely won't happen.  Assuming each element of the stream comes randomly and independently from some distribution, then it is exponentially unlikely that the case you mention happens.

How do you train from a stream?  Easy: each time you see an example, you update the weights of the neural network following the rules of gradient descent, then throw away that example.  In this way, the weights of the neural network change over time, and you don't need to store any past examples.  Over time, as you've seen enough examples, this should converge to a neural network that performs about as well as possible on the data, assuming that all of the data in the stream comes from the same distribution.