My question is the following: is there always, for any non-directed graph $G$, a choice of generators of the fundamental group or, more in general, a set of cycles, covering the graph and with the property that no edge is shared by more than two cycles?
In case it isn't always possible to find such a set, can you provide a counter-example?
The answer to your first question is no: for the complete graph $K_n$, the fundamental group needs $\binom n2 - (n-1) = \binom{n-1}2$ generators. Each one uses at least $3$ edges, for at least $3\binom{n-1}{2}$ edges total. But $3\binom{n-1}{2} > 2\binom n2$ for $n>6$, which means that at least one of the $\binom n2$ edges is used more than twice.
The answer to your second question is also no: if the graph is a tree, we can't cover any edges by cycles, because there are no cycles. More generally, if we take this graph
or any other graph with a cut edge, the cut edge isn't part of any cycle, so we can't cover all the edges by cycles.