How does stochastic gradient descent even work for neural nets? How does stochastic gradient descent (meaning where you backpropagate and adjust the weights and biases of the neural network after each single sample) even work?
Doesn't that just tell the neural network to learn that particular sample? Which isn't really what we want?
So instead of converging towards a solution that appropiately learns the entire training data, the neural net will oscillate between different solutions that are more optimal for the individual samples?
To give you a simple example: say I want my neural network to output $x = 1$ if the input is $1$ and I want it to output $x = 0$ if input is $0$. 
Let's say I train it on the input $0$, then $1$, then $0$ again, and so on. Each time my input is 0, every weight will get adjusted so as to output 0. But then in the next iteration, every weight will get adjusted so as to output 1, hence counter-acting the previous iteration.
 A: You missed the fact that the optimization step is something like new_estimate = previous_estimate + learning_rate  * change, so rather then oscillating, it would gradually average between different solutions. If learning_rate is small, then the increment towards new value will also be small, and there won't be "jumps". Oscillating between different solutions will happen if learning_rate is too big, so if you see this on the training history plot, this suggests that you should lower the learning_rate.
A: The type of problem you're pointing out is what happens when you overfit the training data.  You're actually describing a rather extreme case of overfitting in which the network is adjusted too much for each case, whereas in general people talk about overfitting for the entire set of training data — but the principle is the same.
To avoid overfitting the data, you can adjust the "learning rate" which is essentially a measure of how much you adjust the weights in each step of learning.  So using your example cases, every time the input is 0 the weights will only be adjusted so that the output is closer to 0 (how close is a factor of the learning rate.)  The idea is that by making small enough adjustments, you'll avoid the kind of oscillating / overfitting behavior you're describing.
A: The outputs won't be 0 or 1.  Even if you use a linear (identity) link on the output side, the output would be like a yhat from regression, but not 0 or 1.  Further, the connection weights are e.g. initialized to small random numbers in the range [-0.5,0.5], so with random connection weights at the first iteration, how can the predicted output be 0 or 1?  Same thing for logistic, tanh, and softmax activation functions on the output side.  
For an identity link function on the output side if the result is binary (0,1), I usually use (-1,1) instead.  ANNs also like inputs to be balanced in a range of [-1,1]  or at least mean-zero standardized.  So feeding 0,1's to an ANN could be throwing you off.  You're also supposed to permute (randomly shuffle, or reorder) the input records that are fed to an ANN, so the ANN does not learn from the order of the data.  I do this before each sweep (epoch) through the training data, since I don't want the ANN to learn from training object order.  
After you train the ANN on the training data, you predict class (0,1) with objects held out of training that are in each CV fold.  Prediction accuracy is never based on predicting the output for objects used in training.  (they are used internally, but it's only for training error: MSE or cross-entropy).        
A: Your full data is almost always a sample itself unless you truly got the population which is rare. It should be easier now for you to get comfortable with an idea that a batch is the same in some sense as the full data set, except for the size.
The caveat here is that the batch should preserve the characteristics of the full data set. Imagine, that you're building a face recognition data set. If your batch first takes all black women, then white women, then white men and finally black men, it's not a good situation, because the batches will be have different characteristics than the sample. Ideally the batches are sampled randomly from the full set, and the full set itself is a random sample from the population
