Deriving the Lagrangian for a free particle
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$
For more on Galilean invariance, see also this Phys.SE post.
Qmechanic's answer is good, and I only want to comment (but I can't) on two small mistakes in the logic of the derivation for the first part, but which doesn't affect the final answer.
From $(2)$ we see that $\vec{a} \approx \vec{0}$ solves the equation. Now, assuming that $\vec{a} \neq \vec{0}$, then we get the statement that on-shell $\vec{a} ~||~ \vec{v}$. After all, there is no notion of vectors being 'parallel' if one of them is the zero vector.
The next statement is not gotten by taking the length on both sides of the equation. This is because we don't know if $|\vec{x} + \vec{y} | = |\vec{x}|+|\vec{y}|$ or $|\vec{x}|-|\vec{y}|$. The former is when the two vectors are pointing in the same direction and the latter is when they are pointing in opposite directions.
Instead, dot with $\vec{v}$. Then one gets \begin{align} 2(\vec{a}.\vec{v})(l'+2v^2 l'') \approx 0, \end{align} whereby from the assumption that neither $\vec{a}$ nor $\vec{v}$ are identically 0, the stuff in the other paranthesis vanishes. Then the result that this branch is bad follows, leaving us with $\vec{a} \approx \vec{0}$.
Hope that was useful :)
Also Qmechanic gave the correct answer, I believe it is overloaded, because there is actually no need to use motion equations (Euler-Lagrange equations) to answer to the second part of the OP question at least.
Actually you can simply just generalize original Landau approach to this issue for an answer, so I will mention it here in details:
Lets suppose that $L\left(\vec{v}^{2n}\right)$($2n$ is to have scalar value) is the Lagrangian of a free particle in inertial frame $K$. suppose another inertial frames of reference $K'$ that moves relative to $K$ with infinitesimal velocity $\vec{\varepsilon}$, the Lagrangian $L'=L\left[\left(\vec{v}+\vec{\varepsilon}\right)^{2n}\right]$ in $K'$ that describes the particle should be same Lagrangian as in $K$ up to a total time derivative.
To show that, we expand $\left(\vec{v}+\vec{\varepsilon}\right)^{2n}$ in first order of $\vec{\varepsilon}$, to find it, we suppose at first that $n=1$, then: $$\left(\vec{v}+\vec{\varepsilon}\right)^{2}\simeq v^{2}+2\vec{\varepsilon}\cdot\vec{v}$$ then to find for $n=2$ we write: $$\left(\vec{v}+\vec{\varepsilon}\right)^{4}\simeq\left(v^{2}+2\vec{\varepsilon}\cdot\vec{v}\right)\left(v^{2}+2\vec{\varepsilon}\cdot\vec{v}\right)\simeq v^{4}+4\left(\vec{\varepsilon}\cdot\vec{v}\right)v^{2}$$ repeating this couple times insures you that: $$\left(\vec{v}+\vec{\varepsilon}\right)^{2n}=v^{2n}+2n\left(\vec{\varepsilon}\cdot\vec{v}\right)v^{2n-2}+O\left(\varepsilon^{2}\right)$$ then we can write by expanding the Lagrangian that: $$L\left[\left(\vec{v}+\vec{\varepsilon}\right)^{2n}\right] = L\left(\vec{v}^{2n}\right)+2n\left(\vec{\varepsilon}\cdot\vec{v}\right)v^{2n-2}\frac{\partial L}{\partial\vec{v}^{2n}}+O\left(\varepsilon^{2}\right) \simeq L+g\left(v\right)\sum_{i}\varepsilon_{i}\frac{dx_{i}}{dt}$$ Where: $$g\left(\left\Vert \vec{v}\right\Vert \right)\equiv2n\, v^{2n-2}\frac{\partial L}{\partial v^{2n}}$$ because $L\left(v\right)$, it should be clear that $g$ have to be a function of speed only (not of velocity or it's components), also we see that the sum sign, is actually already a full time derivative by it's own, so to keep the second term full time derivative, we see that the only possible option for us it to have $g\left(v\right)=const$, from this it follows immediately that $n=1$ (note that $n>0$) and $L=\alpha v^{2}+\beta$.