Howdy Todd,
I'm going to type up some suggestions and ideas, but keep in mind that everything I type is just a suggestion, and that of course you know your situation better than anyone else on this board. Use what's helpful for you and discard whatever isn't.
Let's look at the Excelsior ADN/AASN. First of all, the only difference between the two is that with the AASN you can do seven classes as free electives (meaning you could find away to use some FEMA classes for that). The program has two parts, one flexible, and one non-flexible. There are 31 hours of General Ed and 36 hours of Nursing specific exams.
Costs: At a bare minimum for the program, you're going to need to spend:
Application: $75
Enrollment: $895
Graduation: $495
Nursing Theory Exams :$250 * 8 exams: $2000
Focused Clinical Competencies Assessment (FCCA): $390
Clinical Performance in Nursing Examination (CPNE): $2025
So without any other costs at all, you're going to have to spend at least $5880 on Excelsior itself. I don't want to discourage you from this program, but I want to make sure we brought that up.
General education:
Written English :3 Credits. You mentioned that you were considering doing straighterline for this requirement, so I'm going to assume that you still do. We'll assume that you can do the course in one month (pretty easy if it's all you're doing) and budget $140 ($99 a month plus $39 a course)
Information Literacy: 1 Credit. If you can still use Penn Foster, you can do this for about $100, or you can just pay Excelsior for one more credit. Either way, the course is insanely easy.
Humanities and Humanities Core :6 Credits. I would strongly recommend you consider the Analyzing and Interpreting Literature CLEP exam for this requirement. It's an easy enough exam, and worth a full six credits $100
Lifespan development: 3 Credits. This is an easy enough CLEP with a little study and instacert. $100
Sociology: 3 Credits Among the easiest of CLEPs, studying for it along with the Lifespan development will allow you to also practice for the general psych Clep. $100
Anatomy and Physiology: 4 Credits. There are two ways I would recommend you consider for this exam. The exam would likely be quicker and less work, but more expensive and the possibility of failing the exam. $355. The alternative would be to purchase the Straighterline Anatomy and Physiology courses that begin in 2011 and do them while you do the English Composition course. This also gives you some more flexibility for alternative nursing programs if you decide to consider those. Assuming you could also do these in a month each (you can do all three at once), $280
Microbiology: 3 Credits. There are some online courses that you can take for microbiology, but other than that your easiest option would just be to take the excelsior exam. $250
Other science coursework: 1 Credit However you complete your A&P requirement, you'll have some excess credits that will fulfill this sections, so $0
Art and Science Electives : 7 Credits. This is where you things like ALEKS or FEMA come in. You have a lot of options in this area, so I would just stay with the ADN, since there's just not a big enough advantage to taking the slightly easier AASN. I would recommend you take two ALEKS courses over two months and apply the one remaining credit from A&P to this requirement. Be warned, they are difficult, but they can apply to future BA degrees and you can't really beat the price $40.
Essentials of Nursing Care, health safety: 3 Credits. Although this is not actually in the General Education requirements list, I think you should take it as well. You can take it before you enroll at Excelsior and it should give you some sort of idea as to whether or not you will be happy with the program. $250 (but note that I also counted this in the costs above)
You should also consider the excelsior State board requirements as you consider travel. Examine this link:
State Board Requirements - excelsior.edu
Testing locations: It looks like you can take CLEP/DSST/ECE exams in Dhahran, Riyadh, Dammam, and Jubail (and, if you can get access, perhaps US military installations?) I would discourage taking massive amounts of exams at once in the US, since you're not able to take them one at a time.
Recommendations: I would suggest that before you do anything else, you do not enroll in excelsior yet. They're will notify people if they're going to increase the prices, so you'll likely get a heads up on any chance to lock in prices, and since you have all their requirements, there's no need to spend money on that yet. Instead, I would suggest you take the next six months to knock out all of the prerequisites. At the same time, you can consider beginning work on a secondary degree, that would give you a generic bachelor's at the same time. You could transfer most of your eventual Excelsior nursing classes into one of their BA or BS degrees in the future as well. There are also some evaluation options to get credits for your paramedic you could consider.
To summarize
1 course :$100
3 CLEP exams (12 Credits) $300
3 Excelsior Exams:$855
One Straighterline course: $140
Two Aleks Courses:$40
Total: $1435 for 34 credits