The question was answered in the negative on Math Overflow. See https://mathoverflow.net/questions/30759/in-a-graph-is-it-always-possible-to-construct-a-set-of-cycle-bases-with-each-an
Edit:
We get a counterexample from any non-planar graph where every edge is part of at least one cycle. Here's a reference: P. V. O'Neil, Proc. AMS, 37 (2), Feb. 1973, 617-8
I'll repeat the argument here. Take a nonplanar graph with every edge in at least one cycle. If that had a cycle basis like the one you want, then we could generate one for $K_{3,3}$ or $K_{5}$. Suppose we had a basis for $K_{3,3}$. There are 4 cycles in that basis. (A cycle basis has m-n+1 elements, where m is the number of vertices and n is the number of edges.) Also, take the binary sum of the four cycles. The five cycles include every edge exactly twice, so there are a total of 2 $\cdot$ (number of edges) = 18 edges in those five cycles. But each cycle has at least 4 edges, so the five cycles must have at least 20 edges. Contradiction.
Now let's look at $K_{5}$. A cycle basis has 6 cycles. Also take the binary sum. The 7 cycles include each edge exactly twice, so there are 2 $\cdot$ (number of edges) = 20 edges in the collection. But each cycle has at least three edges, so the 7 cycles have at least 7*3=21 edges. Again, a contradiction.