What are food additives that help popsicle/shaved ice melt slower?
You could experiment with decreasing the sugar...higher sugar means quicker melting.  However, if you want to eliminate all melting, you could try making a fluid gel using low acyl gellan (typically 0.5% to 1.25%...so, it doesn't take much). Then freeze that. It is more freeze/thaw stable than agar.