I have got to a reasonable level with mandarin Chinese through on-and-off study over a few years, mostly in my free time. Here is what worked for me.
1) Most important is how much time you put in. Don't worry about the on-and-off, though regular is better. Don't worry too much about efficiency unless you're putting in the hours. For Chinese I estimate I've spent at least 2000 hours studying to get to where I am today.
2) Vocab's important. SRS can help with this. I personally like using online dictionaries and translating the example sentences. Any word you don't understand in an example sentence, look up. It will take a long time, but eventually you will start to remember common words. One day you will get to the stage where you recognise 95% of the words you see, and that's enough to get basic understanding of most material. You'll probably eventually want to aim for about 10,000 words of passive vocabulary. At 10 minutes a word, that's already 1500 hours+, about 40 weeks, 40 hours a week.
3) Mandarin or arabic are languages that many people speak and study. You'll be able to find plenty of material online, videos, radio, news, blogs. TV and radio are probably less efficient if you're not able to read similar material, so try to find material with transcripts or subtitles and use those.
4) Teachers can be helpful, but are expensive. VOIP classes may help with the cost, or living in a country that speaks the language. The main thing teachers will help with are correcting usage mistakes and pronunciation. Working with a teacher is in my opinion not much more efficient (maybe less) than self-study for pure vocab learning, so self-study vocab if you want to save money. Useful exercises are writing essays (ideally by hand) and having them corrected, and reading passages out loud for pronunciation practice. General chat can be helpful for building confidence and because it uses different vocab.
5) There are lots of free resources for learners online. For example, http://www.dliflc.edu/products.html has an Arabic grammar search, and some other Arabic resources if you look for them. It maybe worth trying some of these. Try different language versions of topics in Wikipedia, sometimes the foreign languages are translated directly from the English versions. Or for words you can't find in a dictionary, try doing a search with the target language equivalent of "what's the meaning of xyz".
6) Unfortunately though vocab and time are the limiting factors, so though you may be slightly more efficient with software and specialist podcasts (definitely worth at least trying some free learning site podcasts for arabic, sure there must be some out there), optimise for maximum time spent rather than software bought. While my mandarin is a long way from where I want it to be, I'm reasonably fluent in the basics, and given time I'm confident I'll get there on the rest.
7) I've spent a fair amount on private tuition, but nothing on specialist software, and the textbooks I've bought I haven't used much. A good dictionary will do you just as well as a lot of textbooks, though textbooks won't do any harm, just not essential. So don't worry too much about not having the right tools so long as you are able to figure out example sentences in a dictionary, armed with plenty of patience you'll probably be alright. Incidentally I'd say with today's internet, it's probably less important to go overseas to study than before, although it probably won't hurt (apart from the disruption of moving to a new place). Language partners can help, but if you're aiming for 500 hours of study it's likely that you can earn enough to pay for a teacher for 500 hours in less than 500 hours doing something other than teaching English, so consider this more for fun unless you particularly enjoy teaching people.
8) Don't worry too much about age. Do worry about motivation and the time you spend. Kids grow up in an environment with educational TV shows, parents and teachers correcting their mistakes, and many hours of language classes learning literature, grammar, composition, public speaking, and so on. You can do some but not all of this, but as an adult you have responsibilities and so the limiting factor is likely to be the time you decide to spend on these areas. Try finding kids TV on youtube or equivalents, but realise that it's going to be more expensive and hard to simulate the learning environment of a child compared to a child growing up in the country.
9) You'll forget things if you don't study for a while, native or non-native speaker. But you'll pick them up soon enough when you start studying again. So don't worry too much about that, aim for regular study, but study when you can is better than not at all.
10) Before spending the thousands of hours and the money to learn a language, be clear about your goals and the level you want to attain. You can go anywhere up from understanding a menu and asking someone where they're from to understanding a country's culture and literature and being able to talk fluently with natives. To really get good at a language you'll need to spend a lot of time, this will be easier if you can justify it for reasons beyond just the language, probably professional or personal reasons in the long term.
Put the time in and you'll get there before too long. Have fun.
Edit: http://gloss.dliflc.edu/ has lessons for many languages. Edit2: Karaoke can be fun too - search youtube. Edit3: I like this one: http://www.youtube.com/watch?v=pgElZAj3ePI quite funky, though it's difficult to know if her accent / vocab is standard, it's still fun to try to follow.