Basically alternate between weak, medium and strong attacks as much as possible. You don't have to follow the relevant Deathblow's sequence exactly to learn it. I tend to do something like weak, weak, strong / medium, weak, medium / strong, strong for example. Basically alternate between using primarily weak, medium and strong attacks, saving some AP if you wish to do a combo (though this shouldn't be necessary unless you're up against a boss). You're on the right track though, as learning Deathblows early on is the way to go, as they become available as you level. Though bare in mind some won't appear until you've got at least 7 AP to use, or past a certain point in the storyline.

N.B. You won't get a message to tell you if you're at 100% if the Deathblow in question can't be learned until you are a high enough level, though it will say 100% in your status screen.