Briefly: instead of using trees you should be using implicit (or Crank-Nicholson) PDE schemes. They allow the timesteps to be much larger for a given equity price grid, and allow for boundary conditions to limit the range of equity prices to a realistic regime.
There are (at least) two major markets that have a lot of long-dated american-exercise options: bermudan interest-rate swaptions and convertible bonds. Though I generally agree with Matt that there is good reason to use stochastic vol in these markets, they do not traditionally do so, leaving stochastic vol modeling mainly to exotics desks. Bermudan swaptions, for example, are usually handled in multifactor interest rate models and don't provide a close analogue for your question.
In convertible bonds, the embedded conversion option is exercised at the discretion of the bondholder and typically lasts for many years. This is much closer to what you are asking about. You can therefore get some good inspiration by looking into that literature.
One trick that works (surprisingly?) well is to include random volatility without specifying an extra stochastic factor for it. This is done by linking volatility to the stock price, as in Andersen's paper.
The SDE changes from
$$
\frac{dS}S = r(t) dt + \sigma(t) dW
$$
to
$$
\frac{dS}S = r(t) dt + \sigma(S,t) dW
$$
where we can take a variety of forms for $\sigma$, such as
$$
\sigma(S,t) ={ \sigma(t) \over S^{2}}
$$
The discretization for an implicit PDE solver is then almost exactly as for Black-Scholes.