Can Lagrangian mechanics be justified without referring to Newtonian mechanics? Are there any ways of justifying Lagrangian mechanics as a foundation of classical physics, without referring to Newtonian mechanics? In other words, what is the deeper reason or intuition why 
$$\int_{t_0}^{t_1} T-V$$
must be minimal, beyond the fact that the equations it generates agree with Newtonian mechanics? Is there no deeper reason?
All the resources I've seen (class I took years ago, books, wikipedia, random pdfs) make essentially the same chain of reasoning:
$$\substack{\text{observation}\\ \text{intuition}\\ \text{physical principles} } \implies \text{Newtonian mechanics} \Longleftrightarrow \text{Lagrangian mechanics}$$
This question is basically whether the chain of reasoning be swapped, as follows:
$$\substack{\text{observation}\\ \text{intuition}\\ \text{physical principles} } \overset{?}{\Longrightarrow} \text{Lagrangian mechanics} \Longleftrightarrow \text{Newtonian mechanics}$$
 A: Since the Lagrangian results in exactly the same equations of motion as Newton's laws, I'd say that based on their agreement with experiment both are on equal footing.
Of course, to get the right equations of motion from Lagrange's equation you have to pick the right Lagrangian, so then you ask how we systematically pick the right Lagrangian.
The recipe in mechanics is
$$\mathcal{L} \equiv T -U \, ,$$
so then you ask how we systematically find $T$ and $U$.
From a purely theoretical perspective, finding $T$ and $U$ is on the same level as picking the forms of various forces used in Newton's law.
The practical difference is that force can be defined in a way that relates it to simple experiments, so pedagogically we start with force.
The question specifically asks if observation, intuition, and physical principles naturally lead to the Lagrangian formulation.
One perspective is that the principle of least action is the phsyical principle of the universe, so from that perspective the answer is "yes".
I wouldn't say intuition leads to the Lagrangian formulation, but I also wouldn't say that intuition leads to Newton's law.
It is quite mind-bending when we first learn that an object uninterrupted by external forces moves at constant velocity.
This is unsurprising given how long it took humanity to figure that out!
What about observation?
Certainly the right observations lead naturally to Newton's law.
Put a feather on top of a book and drop them and you'll see the feather fall just as fast as the book.
Push harder on a cart and it speeds up faster.
The Lagrangian formulation doesn't arise from every-day observations like those.
Still, in the end the Lagrangian formulation definitely can come before Newton's laws.
There's nothing more arbitrary or unfounded in dictating the forms of $T$ and $U$ for various systems than there is in dictating the form of $F$ in those same systems, so the answer to the main question of whether the Lagrangian can be developed without talking about Newton's laws is a definite "yes".
Pick any physical system and we most certainly can describe and analyze it with the principle of least action without ever talking about force or Newton's laws.
In fact, there are lots of non-mechanical systems where Newton's laws don't work at all but the principle of least action works amazingly well (e.g. spin, circuits).
Summary: Dictating that physical systems minimize $\int T-U\,dt$ and dictating how write down $T$ and $U$ for each type of system is no more arbitrary than dictating that physical systems obey $F=ma$ and dictating how to write down $F$ for each type of system.
EDIT: As mentioned in the comments, it is possible (and typical in some settings) to guess the form of a Lagrangian for a system based almost entirely from symmetry principles.
This works even for things like Lortentz invariance; you can derive Maxwell's equations from Lorentz invariance, conservation of charge, and some assumptions about the structure of space-time.
This makes the Lagrangian arguably more general than Newton's laws.
That said, it's also possible to guess the form of the Forces for a system from the same symmetry principles, so it's not always really true that the Lagrangian is really more fundamental.
A: With a strong grasp of Lie Algebra and Calculus of variations, "Invariante Variationsprobleme" should provide all the foundation one needs to build Newtonian Mechanics (and so much more). The deeper reason that we use either of these formalism is that they agree with experiment; that either formalism predicts the other is far less valuable than that they predict experimental outcomes.
From an intuition perspective, if you assume that the laws of physics must be the same at any given place, speed, orientation, etc..., you could 'derive' Lagrangian mechanics, but you'd need access to much higher mathematics than simply moving through the 'standard' physics track.
A: 
Can Lagrangian Mechanics be justified without referring back to Newtonian Mechanics?

Sure; one can deduce Newtons Laws from it.
The question is should one? 
By deducing Newtons Laws one is missing the crucial aspect of induction; the reverse procedure and in a sense more difficult; that is the discovery and invention of a theory that covers a wider range of phenomena. 
The concepts that go into Lagrangian Mechanics are those that first appeared in an exact form in Newtonian Mechanics. 
