Shoes are demanding in terms of adhesive requirements. It often involves bonding different materials to each other, including porous materials like leather or fabric to rubber or plastic, which can be hard to bond to. The bond needs to survive continuous flexing, being exposed to high and low temperatures, getting wet with water (or hydrocarbons like gasoline at a filling station), and have a life approaching that of the shoe.
Fortunately, these requirements have been around for a long time, and solutions have been figured out and perfected. There's a good assortment of proven adhesives, some designed specifically for this purpose, that are routinely used to manufacture or repair shoes, including bonding rubber to leather.
Some of what's sold for this purpose are variations on polyurethane glue (like Gorilla Glue), or cyanoacrylate glues (superglue). But the most effective, and what shoe manufacturers and repairers use, are mostly variations of a flexible, rubbery material, like Neoprene, in a solvent.
A very common one used in the industry is Barge Cement. It's sold to professionals/manufacturers by the gallon or drum, but you can find it in small containers at retailers. Others go by names like Shoe Goo, Shoe Fix, Boot Fix, and similar variations on the theme. There are a few general purpose adhesives with a similar formulation (often called "construction adhesives" because of the high bond strength on a variety of materials), like E6000. This link has a list of good adhesives in consumer-sized packaging.
You can find reviews of adhesives for this purpose online. The examples mentioned above are typically at the top of those reviews. I tend to have E6000 on hand because it is generally very good at bonding a wide variety of stuff, and have used it to reglue rubber soles to the leather (these repairs have held up for several years so far and show no signs of deterioration).