It seems to be all about getting a visa with not too many strings. If you can get the visa with just a hotel booking, then technically you ought to be able to arrive by plane and be let loose. As with many countries like this, it's the getting in that counts - once in you're off the radar. It depends on what the Alg-in-Can embassy will be used to. In London for example they are used to/expect a faxed invite from an travel agent that corresponds to a visa app. Hotel booking scam does not seem to work, but it does with other nationalities like Portuguese it seems.
For a while I thought arriving by plane in Alg (the way you are doing it - more chance of success) was a good dodge until one time I arrived and they said at immigration 'where is your escort?!' (there could have been more bombs in Algiers at that time - lately less bombs
in the city that is).
So, if you can get a visa with just an invitation for a hotel (getting an answer was always the crux, but there are one of two who play the game), then you ought to be allowed out the intl airport (immigration) at Algiers, walk to the domestic terminal and get your plane to Beni.
Never heard of 29th parallel; it seems Reganne and In Salah and Hassi M are points where an
unescorted foreign vehicle won't get past. But in Alg it's never cut and dry from year to year or place to place - until it is - usually further south or in a more strict wilaya (province) like Adrar or Ilizzi.
When I have flown direct Europe to Tam (deep south, formerly slack wilaya), one was easily able to get past immigration and out the door, but then getting on a bus out of town would be tricky with checkpoints. In Tam they are used to/expect tour groups flying in, being met by guides and off they go.
Short version: your plan is a good one (would not work in the other direction) but it will help a lot if you look like a local, keep a low profile (from police) and speak French or even Arabic. You will pass through lots of nice towns and great dunes near Kerzaz and north of El G, plus have fun meeting the locals on the bus.
At Taleb Larbi (El Oued border to Tuni) they may be a bit alarmed about how you got there, but by then you will have a feel for the place and a good story.
Ch