You can use gradient descent one example at a time. It still works just fine. The gradients are more unstable, but you will still converge eventually.