You nearly wrote out the proof already. In short: use your info about the subsequences to go far enough along in all of them so that each is $\varepsilon$-close to $L$. Convert those subsequence indices into indices of the original sequence, and take their max. This lets you know how far in the original sequence you have to go to be sure that no matter which subsequence a term belongs to, that subsequence is already close enough to $L$. This can be done as a direct argument.
If we want to show that $\{a_n\}$ converges to $L$, then we need to show that for any $\varepsilon > 0$, $\{a_n\}$ eventually stays within $\varepsilon$ of $L$.
So, pick some such $\varepsilon > 0$ to start. We want to find some $N$ so that $|a_n - L| < \varepsilon$ for all $n > N$.
You've noticed already the key idea that every natural number (index) is of the form $k\cdot m + b$ for some integers $m$ and $b$, so that each term is a member of one of the subsequences. You've also noticed that within each of those subsequences, we are eventually as close to $L$ as we want. That is, for each of these $k$-many subsequences $\{a_{k\cdot n + b}\}$, there is an $N_b$ such that from the $N_b$-th term onward, we are within $\varepsilon$ of $L$. Note that the $N_b$-th term of such subsequences has index $k\cdot N_b + b$ in the original sequence.
So, we can write down the index for each subsequence after which the subsequence is close to $L$, and we know that all terms in the original sequence fall into one of these subsequences. You know somehow that we just need to ensure that we are far enough along our original sequence so that all of the subsequences are close enough.
I guess the one thing you're missing is that, we're lucky here, because there's only finitely many subsequences to worry about. So we can just take the max over the subsequences. That is, if we take $\max\{k\cdot N_b + b\}$ over the different choices of $b$, this will give us an index in the sequence $\{a_n\}$, after which, all terms are members of a subsequence $\{a_{k\cdot n + b}\}$ after the $N_b$-th term, hence close to $L$.
That should be enough to be considered a formal proof (maybe with a bit more explicitly giving the inequality rather than saying "close" where I did), and it's just a direct argument. I suspect your difficulty (since this is where I'm struggling to get good notation :P ) was somehow in the notation for talking about transitioning between terms "so far along" in the subsequences, and "correspondingly far along" in the original sequence.