Some reponses here are close to "do a mathematics degree, then a physics degree". I think this is not what you expected. Learning all that subjects is factible and natural while you are at the university, but trying to adquire all that knowledge alone on your own in your free time, with no professors, no classes, no press to do exams in certain dates... that is almost impossible.
Having said that, I think I understand exactly what you want, because I have had the same question once. I am a physicist, but after my degree, I realized that my understanding of GR from a mathematical point of view was only superficial. So I researched on the question and finally designed a "step by step" bibliography that I am still following in my free time. Here you have it:
1) Start with the old edition of the small Schaum book 'Vector Calculus' by Murray M. Spiegel. It starts with the very basic definition of vectors from high school, and ends with Christoffel Symbols and Geodesics. Every chapter has minimalist description of the essentials, followed by solved exercises. Read only the descriptive part of chapters 1 through 6 (the first 3 or 4 chapters will surely be completely known for you, but it is good to refresh), and then work on the complete chapters 7 (curvilinear coordinates) and 8 (tensor calculus), I mean: study chapters 7 and 8 with the solved exercises too.
Specially work ALL the solved and unsolved exercises of chapter 8.
This can't do miracles (i.e. it cannot be a substitute for a complete degree in mathematics) but it will give you very useful basic mathematical tools in a very short time. If you can do a partial derivate but don't know what means "derive the Christoffel symbols in spherical orthogonal coordinates", this is the book you have to start with.
2) After the Schaum, study the book "The Meaning of Relativity" (1922) by Einstein. It is a book based on a series of lectures he gave in 1921 in Princeton, with progressive explanations from tensor calculus to the Friedman cosmology, including special and general relativity. It is intended to be self-explanatory in the mathematics, but it will have much more meaning to you if you have worked out the Schaum book first. It will require also some short looks at wikipedia if your background in physiscs is not good (i.e. the Poisson equation or Maxwell equations and their meaning when you encounter them) but nothing difficult. The only problem with this book is sometimes the old-fashioned notation or, from time to time, some details you will have to guess (for example, he assumes c=1 for special relativity and it can be very confusing if you haven't noticed). But it is very stimulating to be learning from Einstein itself, and the modern books are in general either too basic, or too biased in one direction.
3) After having worked points 1 and 2, I have now jumped to learning chapters 1 to 6 from the book "General Relativity" by Wald, including the exercises (this is very important) that are solved somewhere in the internet (google for it). This is however quite a hard book, and I sometimes regret not to have used first another text. So I recommend you take here the book "Spacetime and Geometry: An Introduction to General Relativity" by Sean Carroll. It is not as hard as Wald but is rigorous and well explained, and the selection of topics is very interesting.
Another quite direct approach to learn relativity from the beginning may be the book "A First Course in General Relativity" from Schutz. This book is unique in its kind, because it developes a geometrical, rigorous approach, yet progressive and easy, to General Relativity and its mathematical machinery, assuming the target reader barely knows at the beginning how to do a partial derivate and little less more. It has many exercises whose detailed solutions are easy to find in the internet. The very last chapters about black holes and cosmology are only introductory, but if you reach them, you will be in a good position to start more ambitious projects (Carroll, Weinberg, etc). In fact, I am seriously thinking about giving up Wald for the moment, and come back to this book, that I partially used in my degree, and work it out from the beginning. I am sure Roger Penrose holds Wald in one hand and reads in a distracted manner while eating its Corn Flakes in the morning, as you and me do with a newspaper, but for me it is still too abstract...