Even if Spain somehow got Gibraltar back, I doubt Yemen would be on their list of priorities when they have problems with their colonial empire and have few interests in the Indies (besides the Philippines).
The best way to do this is to have a big massive WWI-style war happen earlier on, perhaps in the 1890s, and Spain is part of a big alliance that wins the war against another big alliance. At the peace conference some of the losing alliance's colonies are taken away, and while the big boys in the winning alliance get most of them, junior partners are thrown some bones as well, and Spain happens to get Yemen. Like how Belgium got Rwanda and Burundi after WWI in OTL.
Given British commercial interests were already growing pretty well in Yemen by 1800, the most likely setup is for Britain to be the leader of the losing alliance.