Brian Conrad has a handout (pdf) in which he talks about tensorial maps. In it he notes that one should construct maps independently of bases, but that in order to prove the properties of such maps it made sense to choose bases or spanning sets.
I think this is generally applicable: it seems to me that picking bases should be the last part of your work on a problem, and that it mostly comes in at the level of computation. Bases provide a useful structure to a vector space that enables one to start somewhere, and proofs can be easier to do with them. But if you choose a basis too early on, you have to carry it around for the whole problem, and you might have to show how it transforms. Perhaps you could come up with ideas and proofs using bases, and then edit them to show what's really going on at the level of maps?
In class we recently constructed the determinant of a linear transformation $T:V\rightarrow V$ over and $n$-dimensional vector space V, and to do this we defined the exterior power and used the fact that $T$ became multiplication by a scalar in $\wedge^n(V)$. To be sure, we showed that given a basis $v_1, ...v_n$ of $V$, one would make the single basis element $v_1\wedge\ldots\wedge v_n$ of $\wedge^n(V)$, and used this to give the combinatorial formula for determinant. But the properties of determinant are invariant under change of basis, so we didn't prove them using a basis.
[[apologies for any sloppiness as TeX doesn't seem to be working quite right]]
