In physics, it is often implicitly assumed that the Lagrangian $L=L(\vec{q},\vec{v},t)$ depends smoothly on the (generalized) positions $q^i$, velocities $v^i$, and time $t$, i.e. that the Lagrangian $L$ is a differentiable function. Let us now assume that the Lagrangian is of the form
$$L~=~\ell\left(v^2\right),\qquad\qquad v~:=~|\vec{v}|,\tag{1}$$
where $\ell$ is a differentiable function. The equations of motion (eom) become
$$ \vec{0}~=~\frac{\partial L}{\partial \vec{q}}
~\approx~\frac{\mathrm d}{\mathrm dt}\frac{\partial L}{\partial \vec{v}}
~=~\frac{\mathrm d }{\mathrm dt} \left(2\vec{v}~\ell^{\prime}\right)
~=~2\vec{a}~\ell^{\prime}+4\vec{v}~(\vec{a}\cdot\vec{v}) \ell^{\prime\prime}.\tag{2}$$
(Here the $\approx$ symbol means equality modulo eom.) If $\ell$ is a constant function, the eom becomes a trivial identity $\vec{0}\equiv \vec{0}$. This is unacceptable. Hence let us assume from now on that $\ell$ is not a constant function. This means that generically $\ell^{\prime}$ is not zero. We conclude from eq. (2) that on-shell
$$\vec{a} \parallel \vec{v},\tag{3}$$
i.e. the vectors $\vec{a}$ and $\vec{v}$ are linearly dependent on-shell. (The words on-shell and off-shell refer to whether eom is satisfied or not.) Therefore by taking the length on both sides of the vector eq. (2), we get
$$ 0~\approx~2a(\ell^{\prime}+2v^2\ell^{\prime\prime}),\qquad\qquad a~:=~|\vec{a}|.\tag{4}$$
This has two branches. The first branch is that there is no acceleration,
$$ \qquad \vec{a}~\approx~\vec{0},\tag{5}$$
or equivalently, a constant velocity. The second branch imposes a condition on the speed $v$,
$$\ell^{\prime}+2v^2\ell^{\prime\prime}~\approx~0.\tag{6}$$
To take the second branch (6) seriously, we must demand that it works for all speeds $v$, not just for a few isolated speeds $v$. Hence eq. (6) becomes a 2nd order ODE for the $\ell$ function. The full solution is precisely OP's counterexample
$$L~=~ \ell\left(v^2\right)~=~\alpha \sqrt{v^2}+\beta~=~\alpha v+\beta,\tag{7}$$
where $\alpha$ and $\beta$ are two integration constants. This is differentiable wrt. the speed $v=|\vec{v}|$, but it is not differentiable wrt. the velocity $\vec{v}$ at $\vec{v}=\vec{0}$ if $\alpha\neq 0$. Therefore the second branch (6) is discarded. Thus the eom is the standard first branch (5). $\Box$
Firstly, the definition of form invariance is discussed in this Phys.SE post. Concretely, Landau and Lifshitz mean by form invariance that if the Lagrangian is
$$L~=~\ell\left(v^2\right)\tag{8}$$
in the frame $K$, it should be
$$L^\prime~=~\ell\left(v^{\prime 2}\right)\tag{9}$$
in the frame $K^{\prime}$. Here
$$\vec{v}^{\prime }~=~\vec{v}+\vec{\epsilon}\tag{10}$$
is a Galilean transformation.
Secondly, OP asks if adding a total time derivative to the Lagrangian
$$L ~\longrightarrow~ L+\frac{\mathrm dF}{\mathrm dt}\tag{11}$$
is the the only thing that would not change the eom? No, e.g. scaling the Lagrangian
$$L ~\longrightarrow~ \alpha L\tag{12}$$
with an overall factor $\alpha$ also leaves the eom unaltered. See also Wikibooks. However, we already know that all Lagrangians of the form (8) and (9) lead to the same eom (5). (Recall that acceleration is an absolute notion under Galilean transformations.)
Instead, I interpret the argument of Landau and Lifshitz as that they want to manifestly implement Galilean invariance via Noether Theorem by requiring that an (infinitesimal) change
$$ \Delta L~:=~L^\prime-L ~=~2(\vec{v}\cdot\vec{\epsilon})\ell^{\prime} \tag{13}$$
of the Lagrangian is always a total time derivative
$$\Delta L~=~\frac{\mathrm dF}{\mathrm dt}\tag{14}$$
even off-shell.
Question: In general, how do we know/correctly identify if an expression $\Delta L$ is a total time derivative (14), or not?
Example: The expression $q^2 +2t\vec{q}\cdot \vec{v}$ happens to be a total time derivative, but this fact may be easy to miss at a first glance. The lesson is that one should be very careful in claiming that a total time derivative must be on such and such form. It is easy to overlook possibilities.
Well, one surefire (albeit admittedly a bit heavy-handed) test is to apply the Euler-Lagrange operator on the expression (13), and check if it is identically zero off-shell, or not. (Amusingly, this test actually happens to be both a necessary and sufficient condition, but that's another story.) We calculate:
$$\begin{align} \vec{0} &~=~ \frac{\mathrm d}{\mathrm dt}\frac{\partial \Delta L}{\partial \vec{v}} -\frac{\partial \Delta L}{\partial \vec{q}} \\ &~=~4\vec{\epsilon}~(\vec{a}\cdot\vec{v}) \ell^{\prime\prime}
+4\vec{v}~(\vec{a}\cdot\vec{\epsilon}) \ell^{\prime\prime}
+4\vec{a}~(\vec{v}\cdot\vec{\epsilon}) \ell^{\prime\prime}
+8\vec{v}~(\vec{v}\cdot\vec{\epsilon})(\vec{a}\cdot\vec{v}) \ell^{\prime\prime\prime}. \tag{15}\end{align}$$
Since eq. (15) should hold for any off-shell configuration, we can e.g. pick
$$ \vec{a}~\parallel~\vec{v}~\perp~\vec{\epsilon}.\tag{16}$$
Then eq. (15) reduces to
$$ \vec{0}~=~ 4\vec{\epsilon} ~(\pm a v) \ell^{\prime\prime}. \tag{17}$$
We may assume that $\vec{\epsilon}\neq\vec{0}$. Arbitrariness of $a$ and $v$ implies that
$$\ell^{\prime\prime}~=~0.\tag{18}$$
(Conversely, it is easy to check that eq. (18) implies eq. (15).)
The full solution to eq. (18) is the standard non-relativistic Lagrangian for a free particle,
$$L~=~ \ell\left(v^2\right)~=~\alpha v^2+\beta, \tag{19}$$
where $\alpha$ and $\beta$ are two integration constants. Eq. (19) is the main result. Alternatively, the main result (19) follows directly from the following Lemma.
Lemma: If $F(\vec{q}, \vec{v}, \vec{a}, \vec{j}, \ldots, t)$ in eq. (14) is a local function, and if $\Delta L(\vec{q}, \vec{v}, \vec{a}, \vec{j}, \ldots, t)$ does not depend on higher time derivatives $\vec{a}$, $\vec{j}$, $\ldots$, then $F$ cannot not depend on time derivatives $\vec{v}, \vec{a}, \vec{j}, \ldots$. This in turn implies that $\Delta L(\vec{q}, \vec{v}, t)$ is an affine function of $\vec{v}$.
We leave the proof of the Lemma as an exercise to the reader.
The Lemma and eq. (13) yield that $\ell^{\prime}$ is independent of $\vec{v}$, which again leads to the main result (19). $\Box$
Best Answer
The answer is No, OP's argument(v1) is not enough to derive the Lagrangian for a non-relativistic free particle. It is true that the constant of motion mentioned by OP
$$\vec{c}~:=~\frac{\partial L}{\partial \vec{v}}~=~2\vec{v}~\ell^{\prime}$$
does not depend on time $t$. (It is in fact the canonical/conjugate momentum, which in general is different from the mechanical/kinetic momentum $m\vec{v}$.) However, $\vec{c}$ could still depend on e.g. the initial velocity of the particle (which is also the velocity $\vec{v}$, since we know that the velocity is constant for a free particle, cf. e.g. the first part of the linked answer).
This is perhaps best illustrated by taking a simple example, say
$$L~=~\ell(v^2)~=~ v^4.$$
Then
$$\vec{c}~=~2\vec{v}~\ell^{\prime} ~=~4\vec{v}~v^2,$$
which is a constant of motion, as it should be.