Yhea, that's not a workable approach. Seriously, Flamel is centuries old and has had the key to eternal life for all of that. and the largest hoard of lore on the planet for most of it. Trying to legilimency that mind has the most likely result of you becoming a drooling vegetable.

The relevant section (Ch 108):

Next you will ask why I did not kidnap, torture, and kill Perenelle after I learned the truth."

This had not in fact been a question that had come into Harry's mind.

Professor Quirrell continued to speak. "The answer is that Perenelle had foreseen and forestalled the ambitions of Dark Wizards like myself. 'Nicholas Flamel' publicly took Unbreakable Vows not to be coerced by any means into relinquishing his Stone - to guard immortality from the covetous, he claimed, as if that were a public service. I was afraid the Stone would be lost forever, if Perenelle died without saying where it was hidden, and her Vow prevented attempts at torture.

Perenelle's safety relied on the Stone's uniqueness and hiddenness, which is no longer a factor as far as Quirrell is concerned.

I did not attack her directly, for I was not sure of my great creation; it was not impossible that I would someday need to go begging to her for a dollop of reversed age.

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".

1. Voldemort is unlikely to destroy what he could instead steal.
2. Voldemort is unlikely to leave power around where others can find it (and then use it against him).
3. There are potentially many vengeance spells that Flamel has set up in order to dissuade anyone from killing them.

The obvious plan is to steal Flamel's lore and then induce Flamel to commit suicide. Legilimency serves for both purposes. This may be blocked by Occlumency or Dumbledore's intervention, but using a controlled minion to simply kill Flamel seems to go against point 1.