So after pondering Kog's awful Ult most of the day-

-I think I might have a solution that keeps the execute concept without making it feel like a waste of mana to use against healthy targets.

Step 1) Increase the duration of the debuff it places from 2 to 4 seconds

Step 2) Make it so Kog's basic attacks against debuffed targets deal (percentage) of their current HP OnHit

Why?

Well, for one Kog is in desperate need of more mid-game power right now in order for Juggermaw to work. He also needs a reason to be Ulting healthy targets. By attaching a %current HP OnHit to his Ult debuff, it fills both of those needs. Now Kog wants to start by tagging a target with his Ult so he can grind down their HP more quickly so that the execute portion of the skill comes into play. If a route like this were taken, it would probably be a decent idea to swap back over to the x3 damage against foes below 25% health since there's now a non-poke reason for Kog to be using his Ult on things.