Exhausting all $N$ samples before being able to repeat a sample means that the process is not independent. However, the process is still stochastic.
Consider a shuffled deck of cards. You look at the top card and see $\mathsf{A}\spadesuit$ (Ace of Spades), and set it aside. You'll never see another $\mathsf{A}\spadesuit$ in the whole deck. However, you don't know anything about the ordering of the remaining 51 cards, because the deck is shuffled. In this sense, the remainder of the deck still has a random order. The next card could be a $\mathsf{2}\color{red}{\heartsuit}$ or $\mathsf{J}\clubsuit$. You don't know for sure; all you do know is that the next card isn't the Ace of Spades, because you've put the only $\mathsf{A}\spadesuit$ face-up somewhere else.
In the scenario you outline, you're suggesting looking at the top card and then shuffling it into the deck again. This implies that the probability of seeing the $\mathsf{A}\spadesuit$ is independent of the previously-observed cards. Independence of events is an important attribute in probability theory, but it is not required to define a random process.
You might wonder why a person would want to construct mini-batches using the non-independent strategy. That question is answered here: Why do neural network researchers care about epochs?