Rearranging the inequality yields
$$\left(\frac{kv+g}{k^2}\right) \left(1 - e^{-kt}\right) < \left(\frac{kv+g}{k}\right)t - \frac{1}{2}gt^2.\tag{1}$$
So it's clear that it can only hold for small enough $t$, since the right hand side becomes negative for large $t$.
For small positive $t$, rewriting both sides as the integral of their derivatives shows the inequality follows from
$$\frac{kv+g}{k}e^{-kt} < \frac{kv+g}{k} - gt$$
or
$$gt < \frac{kv+g}{k}(1 - e^{-kt}).$$
Now, $1 - e^{-x} > x - \frac{x^2}{2}$ for $x > 0$, so
$$\frac{kv+g}{k}(1-e^{-kt}) > \frac{kv+g}{k}\left(kt - \frac{k^2t^2}{2}\right) = gt + kvt -\frac{(kv+g)k}{2}t^2$$
and $$kv - \frac{(kv+g)k}{2}t > 0$$ yields the inequality for
$$t < \frac{2kv}{(kv+g)k}.$$
The shape of the functions in $(1)$ makes it clear that there is exactly one $t_1 > 0$ at which equality holds, so $(1)$ holds for $0 < t < t_1$. Finding the (approximate) value of $t_1$, if desired, would probably best be done by a root-finding algorithm like Newton's method.
In response to the edit that the inequality should hold for
$$\varphi(t) := \frac{kv+g}{k^2}\left(1 - e^{-kt}\right) - \frac{g}{k}t > 0,$$
we see that the positive zero of $\psi(t) := vt - \frac12 gt^2$ is $t_0 = \frac{2v}{g}$. A computation (see below) shows that $\varphi(t_0) < 0$, so the positive zero $t_1$ of $\varphi$ is smaller than $t_0$, whence $\psi(t_1) > 0$.
Since $\psi - \varphi$ has only one positive zero(1), it follows that $\varphi(t) < \psi(t)$ for $0 < t < t_1$.
(1) $(\psi - \varphi)''(t) = (kv+g)e^{-kt} - g$. In particular, $(\psi-\varphi)''(0) = kv > 0$, and $(\psi-\varphi)''$ is strictly decreasing with asymptote $-g$.
So $\psi - \varphi$ is strictly convex and strictly increasing for $t < t_2 := \frac1k \log \frac{kv+g}{g}$, and strictly concave for $t > t_2$ (still strictly increasing for a while). A strictly concave function that is positive at $x$ can have at most one zero larger than $x$.
Verification of $\varphi(t_0) < 0$:
$$\begin{align}
\varphi(t_0) &< 0\\
\iff \frac{kv+g}{k^2}\left(1 - e^{-2kv/g}\right) &< \frac{2v}{k}\\
\iff 1 - e^{-2kv/g} &< \frac{2kv}{kv+g}\\
\iff 1-\frac{2kv}{kv+g} &< e^{-2kv/g}\\
\iff \frac{g-kv}{g+kv} &< e^{-2kv/g}.
\end{align}$$
Now, if $kv \geqslant g$, that is obviously satisfied. Otherwise, let $x := \frac{kv}{g}$. We then need to see that
$$\frac{1-x}{1+x} < e^{-2x}.$$
This holds for $0 < x < 1$, since
$$\begin{align}
\frac{d}{ds}\left((1+s)e^{-s} - (1-s)e^s\right) =s(e^s - e^{-s}) &> 0\\
\Rightarrow \int_0^x s(e^s-e^{-s})\,ds &> 0\\
\Rightarrow \left[(1+s)e^{-s} - (1-s)e^s\right]_0^x = (1+x)e^{-x}-(1-x)e^x &> 0\\
\iff (1+x)e^{-x} &> (1-x)e^x\\
\iff e^{-2x} &> \frac{1-x}{1+x}.
\end{align}$$
You should re-state this with some absolute value or vector magnitude bars in there, and maybe requiring that the projectile be fired downwards.
– Sparr Aug 30 '13 at 17:15