My favorite book, that I strongly recommend despite the high price of around $100 in the US is "Mathematical Proofs" by Chartrand.
You can get an international copy off eBay for around $45.
If you're weak on basic algebra etc, then you should instead start with "engineering mathematics" by Stroud, which has a foundations section that I started with several years ago when I started relearning math. It's designed for self-study.
I actually did find it helpful to do classes, I found most of the lower division math classes available online (i.e. calculus 1,2,3 and linear algebra). Sometimes, it helps to have deadlines, exams etc :)
Btw, if anyone out there already has a non math degree, but wants to study upper division and graduate level math formally, it turns out the way that is usually done on the US is to apply to a Math Masters program for "conditional admission" to the masters programs. They admit you, and then you do the upper division undergrad courses first, then move onto the masters programs. It's also possible to sign up for one-off classes at various universities via some kind of "open university" program, which is much easier to get into than formal admission to a degree course- I'm actually starting an Analysis course and a Linear algebra course at Berkeley tomorrow, as part of their "summer session", and you basically just sign up, pay your money, and turn up :)
Feel free to get in touch if anyone has any questions (email in profile)