A lot of the advice here is good (and a little bit of it is terrible).
It's definitely not hard, in a period of years, to become an able and accomplished programmer in any modern language. The difficulty will be telegraphing that fact without a formal credential, and that's the reason that most people will want to see a degree. It's certainly possible to get going without a degree -- krellin's right -- but you should consider the economics of it: is the time you'll spend underpaid relative to your skill level worth the time and money you'll spend not getting a degree?
One path you could consider is some variant of the following:
(1) Spend a year or two intensively learning programming, while working a job / not being completely poor. (Hard to do, time management etc.)
(2) Convince some public university somewhere (i.e., somewhere cheap) to let you take a junior/senior course or two, demonstrating an ability to excel in the academic CS environment, and learning some of the tougher stuff about algorithms.
(3) Apply for a Master's program in CS. They don't all require a BS in computer science. They would likely require a few "leveling" courses.
This way, you don't waste time getting another BS, and you still get a CS degree.
One thing about teaching yourself: there are definitely points where that's going to become tougher than taking courses. Examples include studying algorithms in depth, and so on, which are essentially quite intensive math pursuits where the structure of a course can be very helpful. Anybody can learn to program, and program well, but higher-end employers are definitely going to want you to be able to say why mergesort is sometimes better than quicksort, or to describe Dijkstra's algorithm.
As for languages to learn first -- I really agree C++ is a great language to learn. It's the most flexible and powerful modern language, it's in very wide use, and it's relatively hard, so moving to other languages is typically easier than the reverse. I think it's a fine language to begin with (you can start with a subset and slowly grow to the whole thing), but there's nothing wrong with doing python or something first for a while and then moving. I started in Visual Basic years and years ago when that wasn't a ridiculous thing to do, and within a year got frustrated with its limitations and switched to C++. I don't have any regrets.
Sorry, I don't know any good free resources off hand -- you could do better googling that question and following the results. I'd really recommend getting a good book, though. If you're spending a few years on this, $50 for a good book is a tiny additional cost.
@Draug,
"@roller - I'm a C# and Java coder by day, but love C++ for game/graphics design."
Remind me please why, when I posted a C++ program here awhile back, you mistook it for PHP?