Hartle tries to present as much physics as possible before introducing tensors. His book is also among the most up to date. The place to start for GR, though I'd want to have a good grounding in SR first.
Yeah most of the GR textbooks (even Wald) introduce the math needed along the way including tensors, tetrads, tangent spaces, covariant derivaties, Lie derivatives etc etc
As Daverz mentioned the most gentle introduction is Hartle, I think it only presumes calculus. After that either Schutz or Ohanion are good for an advanced undergrad text. In between undergrad and grad stands Carroll and MTW (Misner, Wheeler, Thorne), and they are suitable for a senior or a first year grad student. And then THE grad text is Wald. All of them start from scratch, but they have increasing levels of mathematical sophistication.
I learnt from Cheng, which is a nice book on the same level as Hartle if you don't want too many details. It doesn't cover Black Holes in detail, but covers more Cosmology than Hartle. I studied from it because I wanted Cosmology.
Hartle is better, from what I've seen, but Cheng's book has only 300 pages, as opposed to Hartle's 600+. (I was a little short of time, because of a 15-day summer school.)