Agar agar and gelatin are options, but as you said, you don't want to use them because they change the texture of your popsicles.
Here is a suggestion that would technically slow down the melting process of your popsicles, but the differences might be too negligible to notice:
Instead of an additive, how about removing an ingredient (air) instead? Freeze your popsicles slowly (at around 0 degrees Celsius), to minimize the amount of air trapped inside them. It also ensures larger crystals within the popsicles, as opposed to tiny crystals. Then freeze at the lowest possible temperature to ensure they stay colder longer.