Why is this a first integral? - particle near Schwarzschild black hole

OP's phenomenon is much more general than the Schwarzschild solution. This happens e.g. whenever the Lagrangian $L(y,\dot{y},\lambda)$ satisfies the following 2 conditions:

1. If $L$ does not depend explicitly on $\lambda$, then the energy $$h~:=~\left(\dot{y}^i\frac{\partial }{\partial\dot{y}^i} -1\right)L \tag{1}$$ is a constant of motion (COM)/first integral (FI), cf. Noether's theorem.

2. If moreover $L$ is homogeneous in the velocities $\dot{y}$ of weight $w\neq 1$, then the Lagrangian $$L~\stackrel{(1)}{=}~\frac{h}{w-1}\tag{2}$$ is also a COM/FI as well!

See also this related Math.SE post.

An integral of motion is anything that is conserved during the entire motion. The Lagrangian in this case is one such quantity. You don't want to calculate $\dot{r}\frac{\partial L}{\partial \dot{r}} - L=constant,$ because as you stated, this is valid for a variable doesn't appear in the Lagrangian. This is not the case for $r$, so $\partial L/\partial r$ isn't zero, and the formula doesn't give an integral of motion. What you want is $$\dot{t}\frac{\partial L}{\partial \dot{t}} - L=constant,$$ because there is no explicit dependence on $t$ in the Lagrangian, this is the constant you will use.

Edit concerning the use of the relation $\dot{r}\frac{\partial L}{\partial \dot{r}} - L=constant$. I think this quantity will indeed be constant. The reason is seen from derivation of the left hand side we get: $$\frac{d}{d\lambda}\left(\dot{y}\frac{\partial L}{\partial\dot{y}} - L\right)= \ddot{y}\frac{\partial L}{\partial\dot{y}} + \frac{d}{d\lambda}\frac{\partial L}{\partial\dot{y}} - \left[\ddot{y}\frac{\partial L}{\partial\dot{y}} +\frac{\partial L}{\partial y} + \frac{\partial L}{\partial \lambda}\right]. $$ This will be zero if $L$ has no explicit dependence on $\lambda$. I never tried it, but there should be a way to use this (with $y=r$) instead of the one I did, although it would probably be harder. Please notice that not all constants of motion are independent (for example, the Poisson bracket of two constants of motion is always a constant of motion, but usually it won't be independent from the other known constants). In this case you have four conserved quantities (because of the four Killing vectors), and two of them have been used to fix $\theta=\pi/2$ (look up Sean Carroll's great book for more details on this last point) so the constant of motion you find from this method should be a combination of the two that are usually used (that is, the conservation of "energy" and of angular momentum), rather than a new one.