Let's recall why no analytical formula is known for the price of American Put option. This is due to
the early exercise condition, which requires that options's price should be bigger or equal to its
exercise payoff for any $S_t$ at any time $t \le T$ (in other words $V(S_t,t) \ge max(K-S_t, 0)$).
This property is also known as path-dependence, as payoff at maturity
$T$ doesn't depend only on $S_T$, but also on previous values of $S_t$ where it could be potentially
exercised. An arbitrage opportunity exist when this condition is broken: exercise put and instantly buy it back with a net profit OR buy put and instantly exercise.
Early exercise condition is very hard to account for in analytical solution, hence numerical methods
are used. Most popular are Finite Difference and Monte-Carlo. In both cases you explicitly
ensure that put price doesn't fall below the exercise payoff. (Finite difference works well for 1D and
2D problems and is easier to implement, however Monte-Carlo is more stable in higher dimensions but
is harder to code, again due to the early exercise condition.)
In your problem, a new exercise condition is introduced, which is not path-dependent, but random
(distributed exponentially). It might be interpreted as
Replacement for the path-dependent condition. In this case exercise can be initiated only by
some random chance and holder has no right to exercise. As path-dependent condition was lifted,
we have a chance for a closed-form solution (assuming $r=q=0$):
$$
E[V] = \int_0^T d\tau \ \lambda e^{-\lambda \tau} \int_0^{K} ds \ (K-S) \ \rho_s(S,\tau)
$$
Here $\rho_s(s,t)$ is distribution density of $S$ at time $t$ in risk-neutral measure:
$$
\rho_s(s,t) = \frac {s_0} {\sqrt{2\pi} \ s\ \sigma\sqrt{t}} \exp\left( - \frac{\left(\ln s / s_0
+ 0.5 \sigma^2 t \right)^2}{2\sigma^2 t}\right)
$$
The last integral is BS price of European Put with maturity $\tau$, hence you need to find
$$
E[V] = \int_0^T dt \ \lambda e^{-\lambda t} \ V_{put}(S_0, t)
$$
Addon to the path-dependent condition. In this case exercise can be initiated by some random chance or by the holder. This is a "loosing" strategy as by randomly exercising we always lose extrinsic value (which is non-negative for American options).
This is more challenging as path-dependence is still present. Not sure if you can incorporate
exercise randomness into finite-difference approach, so what is left is Monte-Carlo. It will be
2D, as you need to simulate both $S_t$ and exercise time $\tau$ (if exercise happens). Otherwise.
it should not be much different from standard American pricing a la Longstaff-Schwartz.
Hopefully, these thoughts will be helpful.