Is implicit and explicit memory a useful distinction? In principle I understand the distinction. Implicit memory is not consciously recollected but has an automatic character i.e. while I'm solving a task in math, I'm automatically using the concept of numbers and maybe even counting which I have stored in my memory. Explicit memory on the other hand is the conscious recollection of particular bits of memory, like explicitly counting up to ten or maybe remembering my birthday.

What I'm wondering is this: Isn't this distinction somewhat arbitrary? Even if I consciously use a certain piece of memory to solve a task, isn't it the case that I still don't know how I manage to access this particular memory? And is this even only about memory? To me it seems that everything can be stored in some way (how I breathe, my birthday and the range of things I do when taking a shower) and isn't that the only type of memory we have? Shouldn't the distinction then be about how we use the things we have memorized? I mean is there evidence that implicit memory is stored in a structurally different way than explicit memory? Or am I focussing on the wrong question?

I'm asking this question out of pure interest as a cognitive linguist who doesn't have much to do with memory right now.
No, the distinction is real, not arbitrary. Implicit and explicit memory show different hallmark behavioral characteristics. A good overview of the difference between explicit and implicit memory is available in the MIT Encyclopedia of the Cognitive Sciences. The wikipedia page on implicit memory also has some useful information.
Perhaps the most important piece of evidence we have for this distinction is not behavioral, but from a double dissociation in neuropsychology: some brain damaged patients have impaired implicit memory but intact explicit memory, whereas others have impaired explicit memory but intact implicit memory (e.g. Gabrieli et al, 1995). This is possible because implicit and explicit memory are thought to have separate neural substrates (e.g. Squire, 1992).
There are a lot of questions in your second paragraph and I'm not quite sure I follow. But to be clear, implicit/explicit memory is not the only distinction one can make on memory systems. It is one of many.

Gabrieli, J. D., Fleischman, D. A., Keane, M. M., Reminger, S. L., &amp; Morrell, F. (1995). Double dissociation between memory systems underlying explicit and implicit memory in the human brain. Psychological Science, 6(2), 76-82.
Squire, L. R. (1992). Memory and the hippocampus: a synthesis from findings with rats, monkeys, and humans. Psychological review, 99(2), 195.
Chicago