Lien, one suggestion I have made but never used myself is try the Mercure near Algiers airport - one of the few 'international' hotels in Alg with overseas connections (part of Accor group).
You can book with them online - have a print out as proof - and hopefully cancel once you have the visa.

Any local less expensive hotel probably won't answer (in my experience many years ago).

Ch

Most full-rate rooms booked on the Accor website can be cancelled online till 6pm on the day before arrival, and free cancellaton is clearly indicated in the room/rate listing. However read the rate terms and conditions to be sure before booking. They will ask for a credit card number to confirm booking, but that will not be charged until you actually check in to the hotel.

PS: did stay at the Mercure for a night last year, a balatant ripoff even at the special rates I received, but with a midnight arrival to ALG I was in no mood for a downtown adventure...

status update 28 September 2012
 

I crossed the borders from Tabarka, Tunisia into Algeria at 3 September 2012.

I slept at peoples houses at Annaba, Setif, 2 in Algiers, Tizi Ouzou, Gouraya.

I slept in Hotels in Constantine, Algiers, Oran. I visited Casbah in Algiers with a tourist guide. I visited Grand Kabyle with an Algerian friend who is driving a Moto to.

I had a great time and met very friendly people everywhere.

I passed at avery village or city multiple checkpoints of Police, Gendarme and military checkpoints. This takes a lot of time but its worth the explaining and waiting. They are surprised to find a tourist on a moto traveling alone.

I will leave Oran at 3 October and go to Alicante/Spain.

Maybe I will give a presentation of my travel at the HU meeting in October in Germany.

Now I need to enjoy the last few days here!

Bye

2 days left in Algeria
 

My friend Nasrine is the one who gave me the confidence that it was possible to travel to Algeria!!!

All other people how I interviewed before my travel and who (think) they now Algeria explained that it was to dangerous, impossible to get a Visa and impossible to drive on a motorcycle without a guide. The wer very wrong!

I got my Visa and was driving with my motorcycle from Tunisia to Annaba, Constantine, Setif, Algiers, Tizi Ouzou, Béjaïa, Oran and a lot off small villages. Part of the trip I was driving with a new Algerian friend. He is a rally driver on a dual sport motorcycle to. Whit him I was driving from the Tunisian border to Annaba, I visited the province Kabylia and there I visited Tizi Ouzou and Béjaïa was driving from Algiers to Oran.

I passed many Police, Gendarme and Military checkpoints. In the mountains of Annaba the Military blocked my way to Chetaibi. Once the Gendarme pulled out of the mountains south of Algiers. They guided me back to a Village with two Nissan patrols and one tank. Then I got under "heavy fire" of the chief at the police station for 3 hours. After I left the chief was very nice and he said he hopes that I will come back to Algeria. This is part of my adventure to.

I have been hosted and met a lot of Couchsurfers in Annaba, Constantine, Setif, Algiers and Oran. I got Invited and Hosted by my new Algerian friend. I only stayed a few times in a Hotel, but if I wanted I could be hosted every single day. Algerian people are very friendly and hospitable.

I have a lot of new friends now. I am asked by many people to come back to Algeria. I will definitely do so. Next visit I want to go the South of Algeria, to the Sahara.

30 days is way to short to understand Algeria!!!! I only got a small impression. I'm looking forward to come back!!!!

Algeria is not a touristic Country. Traveling to Algeria means that You need to be patient, improvising but most of all that You are completely dependent on the people. Everyone, even the Police, Gendarme and the Military where every nice to me.

Thank You Nesrine!!!!! Without You I did not visit Algeria!!!!

Guus