OTL the airship flew as soon as the relevant technologies made it practical. Those early German gasoline engines? Installed on Zeppelin's early attempts.
Which were attempts. The Count had to make several, exhausting his own personal fortune and able to make more that finally convinced the military to go ahead and start funding them only with the help of a rather amazing flood of voluntary contributions from the public at large.
And in fact, Zeppelin was focused entirely on airships as military vehicles. The company got its funding almost entirely from military contracts. They did manage a small fleet of airships offering civil flights, true--these were not airlines in that they were not intended to convey passengers from point A to point B; rather they were thrill rides, airborne excursions. One bought a ticket on a Delag Zeppelin to go up into the sky, to see Germany from the air, to be able to say one had done it. In fact the Delag airships were military reserve, their crews were being trained up for military service and were reservists, and when the war broke out the airships were all put into military service at once.
So basically, OTL had all the speculative possibilities suggested--as soon as possible, which was not before 1890.
To meet the challenge, one has to advance the state of the art of metallurgy and engines by 20 years or so. (Or thirty, considering that serious commercial use of airships wasn't really in the cards until after WWI--though I do believe the state of the art as of 1918 was sufficiently advanced to start making passenger ships immediately--and one was built and used for actual air transport by Zeppelin, the LZ-120 Bodensee.
Of course if metals and engines suitable for airships are available for them, they are available for other purposes too--one has probably also advanced the airplane by the same interval.
As for airship operations to overawe tribal peoples--well, the Italians did it some years before WWI, in Libya. (Using the typical Italian preferred approach to the airship, the semirigid). They also pioneered aerial bombing.
The French attempted to enable their reparations airship, rechristened Dixmude, in North Africa, but it blew up one day over the Mediterranean. I've seen it asserted that the French program, being starved of funds, failed to maintain hydrogen purity in the gas cells, and these cells had something like 30 percent air in them--a recipe for sudden flamy disaster!
When the German Afrika-schiff LZ-80 made its epic voyage most of the way to East Africa from Bulgaria, it encountered rough flying over the Sahara and I believe moister parts of Africa too; the thermals boiling off the tropical land during the day made for a different kind of flying weather than pilots used to European or overseas conditions were used to.
It would be very easy for rather arrogant expeditions by colonial powers into hostile native hinterlands by airship to be brought to grief; just one story of how one was brought down in flaming ruin would give all the other groups a lot more confidence in defying them.
So that's a silver lining to the dark cloud of the world's general neglect of the potential of the airship in the 1920s; if the RAF had had them (in the sense of at least maintaining and using the handful they did have, instead of wasting them the way they generally did) and some had indeed started pioneering the Empire Route as planned I guess sooner or later several would have been diverted to colonial operations in places like Iraq (where the British did use airplanes precisely the way some posters here recommend using airships) and probably would have been brought to grief there.