Hands-down, my favorite text is Hoffman and Kunze's Linear Algebra. Chapter 1 is a review of matrices. From then on, everything is integrated. The abstract definition of a vector space is introduced in chapter 2 with a review of field theory. Chapter 3 is all about abstract linear transformations as well as the representation of such transformations as matrices. I'm not going to recount all of the chapters for you, but it seems to be exactly what you want. It's also very flexible for teaching a course. It includes sections on modules and derives the determinant both classically and using the exterior algebra. Normed spaces and inner product spaces are introduced in the second half of the book, and do not depend on some of the more "algebraic" sections (like those mentioned above on modules, tensors, and the exterior algebra).
From what I've been told, H&K has been the standard linear algebra text for the past 30 or so years, although universities have been phasing it out in recent years in favor of more "colorful" books with more emphasis on applications.
Edit: One last thing. I have not heard great things about Axler. While the book achieves its goals of avoiding bases and matrices for almost the entire book, I have heard that students who have taken a course modeled on Axler have a very hard time computing determinants and don't gain a sufficient level of competence with explicit computations using bases, which are also important. Based on your question, it seems like Axler's approach would have exactly the same problems you currently have, but going in the "opposite direction", as it were.
