I) Not all equations of motion (eom) are variational. A famous example is the self-dual five-form in type IIB superstring theory. In classical point mechanics, frictional forces typically lead to non-variational problems.
II) Consider for instance $n$ variable $q^i$ and $n$ eoms,
$$\tag{1} E_i~\approx~ 0, \qquad i~\in~\{1, \ldots, n\}. $$
A simplified version of OP's problem (v3) is the following:
Does there exist an action
$$\tag{2} S[q] ~=~\int{\rm d}t~L$$
such that the Euler-Lagrange derivatives
$$\tag{3} \frac{\delta S}{\delta q^i}~=~E_i $$
precisely become the given $E_i$-functions?
The above restricted problem is relatively easy to answer once and for all, because one may differentiate the known $E_i$-functions to arrive at a set of consistency conditions. Let us for simplicity assume that the functions $E_i=E_i(q)$ do not involve generalized velocities $\dot{q}^i$, accelerations $\ddot{q}^i$, and so forth. Then we may assume that the Lagrangian $L$ does not depend on time derivatives of $q^i$ as well. So the question becomes if
$$\tag{4} \frac{\partial L}{\partial q^i}~=~E_i ? $$
We can collect the information of the eoms in a one-form
$$\tag{5} E~:=~E_i ~{\rm d}q^i.$$
The question rewrites as
$$\tag{6} {\rm d}L~=~E? $$
Hence the Lagrangian $L$ exists if $E$ is an exact one-form.
III) However, the above discussion is in many ways oversimplified. The eoms (1) do not have a unique form! E.g. one may multiply the given $E_i$-functions with an invertible $q$-dependent matrix $A^i{}_j$ such that the eoms (1) equivalently read
$$\tag{7} \sum_{i=1}^n E_i A^i{}_j~\approx~ 0. $$
Or perhaps the system variables $q^i$ should be viewed as a subsystem of a larger system with more dynamical or auxiliary variables?
Ultimately, the main question is whether the eoms have an action principle or not; the particular form of the eoms (that the Euler-Lagrange equations spit out) is not important in this context.
This opens up a lot of possibilities, and it can be very difficult to systematically find an action principle; or conversely, to prove a no-go theorem that a given set of eoms is not variational.
I) OP's questions about the variational principle (e.g. the derivation to and from Newton's laws) are good and interesting questions, but most have been asks before, see e.g. this and this Phys.SE posts and links therein. Lagrangians not of the form Kinetic Energy minus Potential Energy are discussed in this Phys.SE post. The question of whether (or not) a set of equations of motion has an action principle is a duplicate of this Phys.SE post and links therein. Another possible helpful Phys.SE post concerning calculus of variation is this one.
II) The only new ingredient in OP's question seems to be the finite-difference method. Gelfand's use of the finite-difference method seems mostly to be an alternative way to gain insight into the Euler-Lagrange formula for the functional derivative via discretization. It doesn't add anything new to the continuum theory.
For instance, let us for simplicity consider point mechanics (as opposed to field theory). A continuum formulation for point mechanics here refers to a continuous time variable $t$ (as opposed to a discrete time variable). Let there be given a continuum Lagrangian $L(q,v,t)$ that depends on three arguments: position $q$, velocity $v$ and time $t$. Let $\frac{\partial L}{\partial q}$ and $\frac{\partial L}{\partial v}$ denote the derivative wrt. the first and second argument, respectively, and so forth.
Let us approximate the continuum action functional
$$\tag{1} S[q]~:=~\int_{0}^{T} \!\! dt~L(q(t),\dot{q}(t),t)$$
via the following discretized expression
$$\tag{2} S(q_0, \ldots q_{N})~:=~\Delta t\sum_{n=0}^{N-1} L(q_n,v_n,t_n), $$
where
$$\tag{3} \Delta t~:=~ \frac{T}{N}, \qquad t_n ~:= n \Delta t, \qquad q_n~:=~q(t_n),\qquad v_n~:=~\frac{q_{n+1}-q_n}{\Delta t}.$$
In eq. (3) we have chosen the forward difference for $v_n$. Obviously other choices are possible. Then
$$\frac{1}{\Delta t}\frac{\partial S(q_0, \ldots q_{N})}{\partial q_n} $$ $$\tag{4}~=~ \frac{\partial L(q_n,v_n,t_n)}{\partial q} -\frac{1}{\Delta t}\left[\frac{\partial L(q_n,v_n,t_n)}{\partial v}-\frac{\partial L(q_{n-1},v_{n-1},t_{n-1})}{\partial v} \right], $$
where $n\in\{1,2, \ldots,N-2, N-1\}$. Eq. (4) is a discretized version of the Euler-Lagrange formula
$$\tag{5} \frac{\delta S[q]}{\delta q (t)}~=~\frac{\partial L(q(t),\dot{q}(t),t)}{\partial q(t)} - \frac{d}{dt} \frac{\partial L(q(t),\dot{q}(t),t)}{\partial \dot{q}(t)} $$
for the functional derivative$^1$. The functional derivative (5) satisfies by definition the following infinitesimal variation formula
$$\tag{6} \delta S[q] ~:=~S[q+\delta q]- S[q]~=~ \int_{0}^{T} \!\! dt~\frac{\delta S[q]}{\delta q (t)}\delta q(t). $$
--
$^1$ The existence of functional derivative depends on the appropriately imposed boundary conditions, which we have not discussed. In plain English: We need to integrate by part at some point.
Best Answer
If I ask a high school physics student, "I am swinging a ball on a string around my head in a circle. The string is cut. Which way does the ball go?", they will probably tell me that the ball goes straight out - along the direction the string was pointing when it was cut. This is not right; the ball actually goes along a tangent to the circle, not a radius. But the beginning student will probably think this is not natural. How do they lose this instinct? Probably not by one super-awesome explanation. Instead, it's by analyzing more problems, seeing the principles applied in new situations, learning to apply those principles themselves, and gradually, over the course of months or years, building what an undergraduate student considers to be common intuition.
So my guess is no, no one can convince you that the Lagrangian formulation is natural. You will be convinced of that as you continue to study more physics, and if you expect to be convinced of it all at once, you are going to be disappointed. It is enough for now that you understand what you've been taught, and it's good that you're thinking about it. But I doubt anyone can quickly change your mind. You'll have to change it for yourself over time.
That being said, I think the most intuitive way to approach action principles is through the principle of least (i.e. stationary) time in optics. Try Feynman's QED, which gives a good reason to believe that the principle of stationary time is quite natural.
You can go further mathematically by learning the path integral formulation of nonrelativistic quantum mechanics and seeing how it leads to high probability for paths of stationary action.
More importantly, just use Lagrangian mechanics as much as possible, and not just finding equations of motion for twenty different systems. Use it to do interesting things. Learn how to see the relationship between symmetries and conservation laws in the Lagrangian approach. Learn about relativity. Learn how to derive electromagnetism from an action principle - first by studying the Lagrangian for a particle in an electromagnetic field, then by studying the electromagnetic field itself as described by a Lagrange density. Try to explain it to someone - their questions will sharpen your understanding. Check out Leonard Susskind's lectures on YouTube (series 1 and 3 especially). They are the most intuitive source I know for this material.
Read some of the many questions here in the Lagrangian or Noether tags. See if you can figure out their answers, then read the answers people have provided to compare.
If you thought that the Lagrangian approach was wrong, then you might want someone to convince you otherwise. But if you just don't feel comfortable with it yet, you'd be robbing yourself of a great pleasure by not taking the time to learn its intricacies.
Finally, your question is very similar to this one, so check out the answers there as well.