I agree with your assessment of how powerful Perenelle/Flamel (side note: need a good portmanteau a la Quirrellmort) should be, having been able to outwit Baba Yaga in her sixth year and then having six hundred years of excellent leverage to accumulate lore and also maybe play with what the stone can do.

That objection notwithstanding, the most plausible non-Voldemort killer would be Bellatrix, using her superpower of very strict obedience to orders like "Just use AK and do not hesitate for any reason".