Moyes was previously mentioned as a possible successor to Sam Allardyce when he left Newcastle in January.
Deschamps, a former Chelsea team-mate of Magpies executive director Dennis Wise, is available at present.
But Legard believes a link-up between Wise and another former Chelsea team-mate, Gus Poyet - currently assistant manager at Tottenham and the bookmakers' early favourite for the job - is not on the cards.
Keegan confirmed he was leaving St James' Park on Thursday evening after days of speculation about his future.
It leaves Ashley looking for his third manager since taking over in June 2007 - and the club's eighth in 11 years since Keegan's first reign ended in 1997.
Shearer, a legend among Newcastle fans after scoring 192 goals in 363 appearances for the club, has been regularly linked with the manager's job whenever it has become vacant since he retired as a player in 2006.
But he feels that the present set-up - where executive director Dennis Wise is significant in the identification and purchase of new players - prohibits him from being interested right now.
John Toshack believes the conflict leading to Keegan's departure was inevitable
"If you've got three, four, or five players waiting for you and you donít know who they are, then you have got the right to ask yourself 'can I manage this football club?'" Shearer said.
"You live and die by the decisions you make as a manager, and that includes buying players.
"It's a dangerous run when you go into a football club and the director of football is not appointed by yourself.
"There can only be one person who is [ultimately] responsible for buying players."
Moyes, who has yet to sign a new contract with Everton, was among those considered before Keegan returned to St James' Park in January.
Legard said: "Sources in the North-East claim Moyes' name is again in the frame, particularly as his new Everton contract remains unsigned, although I am told that is set to change imminently.
"Whether Moyes would want to work in tandem with Newcastle's director of football Dennis Wise is another matter.
"And whatever his frustrations with Everton's transfer budget, he'll have seen that Newcastle's recent spending power has been flyweight by comparison."
Deschamps, who has also coached Monaco and has previously declared his interest in a job in the Premier League, would fit the club's continental coaching structure.
"Significantly, he's readily available and keen to work in the Premier League," Legard added.
Keegan said his lack of control over Newcastle's transfer policy had been a key factor in his departure and Richard Bevan, chief executive of the League Managers' Association, said the club has to resolve the issue before they appoint a new manager.
"Newcastle failed to create a structure where Kevin Keegan could flourish," Bevan told BBC Radio 4.
"You can't have an orchestra with three conductors. You won't be very successful and people will leave," he said.
MAGPIES' MANAGERIAL TURNOVER
Kevin Keegan: 02/92-01/97
Kenny Dalglish: 01/97-08/98
Ruud Gullit: 08/98-08/99
Sir Bobby Robson: 09/99-08/04
Graeme Souness: 09/04-02/06
Glenn Roeder: 02/06-05/07
Sam Allardyce: 05/07-01/08
Kevin Keegan: 01/08-09/08
"The director of football issue is a broad one.
"If you are going to work with a director of football, what's really important is not whether or not you have one person in charge or not but there is a common purpose and a shared vision and a structure where the manager can actually flourish."
Reports suggest Keegan could be liable to pay Newcastle £2m compensation for resigning just eight months into a three-and-a-half-year contract.
"The dispute between Kevin and the club is in the hands of the lawyers but at no time in our discussions did Kevin talk about compensation," Bevan added.
Keegan's departure has created unrest among the club's fans, who idolise the man who helped them regain their top-flight status as a player and took them to within a whisker of the Premier League title in his first spell as manager.
About 200 angry fans gathered outside St James' Park on Thursday to protest after hearing of his departure, and some were seen scaling the walls attempting to get into the ground.
Since the end of Keegan's first spell as boss in 1997, six other managers have tried to bring a trophy to Newcastle.
Sir Bobby Robson, who spent five years at the helm between September 1999 and August 2004, came close to success.
Robson's side finished fourth, third and fifth in successive seasons and reached the second phase of the Champions League, and the semi-finals of the Uefa and FA Cups.
Kenny Dalglish and Ruud Gullit both guided their teams to FA Cup final defeats, while under Glenn Roeder, they won the derided Intertoto Cup.
But no Newcastle manager has landed meaningful silverware since Joe Harvey's men were victorious in the Fairs Cup in 1969.
Watch the Alan Shearer interview in full on Football Focus: Saturday, 5 September at 1210 BST.
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.