I am looking to do something similar, however I was thinking of starting in Tunisia because Algeria seems to be stacking up quite a few travel warnings for westerners.
Is there something specific that is causing you to want to avoid travelling these areas during Ramadan? My only travel experience was backpacking thru Turkey during Ramadan and it was quite positive. I had a really good time. That being said, I know Turkey is quite different than some of these other areas.
My intent is to start in Tunisia around Late July or early August 2011, I will not have an exact departure date until around May, then proceed east across Libya, into Egypt, then South to Sudan, then to be determined with an eventual arrival in Capetown. I have contacted one Libyan travel agency so far and I am awaiting their response to my travel ideas in Libya. If you have something worked out already I would be glad to join, otherwise I will share my details with you when I have them. If you are interested in all or part of the trip let me know.