How difficult is it to replace this spring without removing the pedal?
You should be able to install that spring without removing the pedal. The biggest issue is you won't have a good view of the backside of the pedal. Watch the video again to see how the spring goes on. You'll have to either do it by feel or put a mirror behind the pedal to help you see what's going on.
But it looks like you have 2 different issues with your pedal. First is the pedal itself feels loose because it pivots very freely on the pedal arm. Adding the spring mentioned in post 3 of this thread will solve that issue.
Second issue is your pedal arm seems to go almost to the floor when you push it, and it doesn't spring back up on it's own. That's related to the aftermarket throttle cable and also possibly your throttle return spring on the carb.
To test if the throttle cable is binding, pop the connector off the ball stud where the cable connects to the carb (circled in red below). Then manually push and pull the cable itself back and forth (red arrows below) to see if there's a lot of resistance. When you push/pull the cable it will be lowering/lifting the gas pedal, so there will be some natural resistance related to that. But the action should still feel smooth.