How to make soft popsicles
The main factors are a gelling agent, alcohol, sugar and air/stirring.


Sugars may decrease the freezig point - add enough sugar and your ice remains soft-ish. Unfortunately this can mean your ice gets too sweet. So instead of using plain sugar, add some "inverted sugar": glucose syrup (aka corn syrup), which stays runny and doesn't crystalize.
You could even take it up a notch and use trehalose, which is basically two linked glucose molecules. It is used in ice-cream making to inhibit the formation of ice crystals. It tastes also less sweet than regular sugar, allowing for less sweet ice cream. Find an award-winning sample recipe here (further down). And if you really must have some hard science, a study on the use of trehalose in ice cream.
Alcohol has a low freezing point. But apart from the question whether you want to use it at all, you should note that you need a certain amount of ethanol to have a noticeable effect - high-proof alcohol and yes, you will taste it. 
Glycerine (a sugar alcohol) helps keep ice cream soft.
Likewise the addition of gelling agents may inhibit the formation of ice crystals - locust bean gum is often used to replace eggs in custard-based ice cream and agar agar and pectin may serve a simmilar purpose.
And finally you can mechanically avoid / hinder the formation of large ice crystals by churning your juice first and freezing the slush instead of pouring the juice straight in the molds. The ice will still be rather hard, but not as much of a "solid icicle", especially if combined with one of the additives above.