In this paper we apply variational energy band theory to a form of the Holstein Hamiltonian in which the influence of lattice vibrations (optical phonons) on both local site energies (local coupling) and transfers of electronic excitations between neighboring sites (nonlocal coupling) is taken into account. A flexible spanning set of orthonormal eigenfunctions of the joint exciton-phonon crystal momentum is used to arrive at a variational estimate (bound) of the ground state energy for every value of the joint crystal momentum, yielding a variational estimate of the lowest polaron energy band across the entire Brillouin zone, as well as the complete set of polaron Bloch functions associated with this band. The variation is implemented numerically, avoiding restrictive assumptions that have limited the scope of previous assaults on the same and similar problems. Polaron energy bands and the structure of the associated Bloch states are studied at general points in the three-dimensional parameter space of the model Hamiltonian (electronic tunneling, local coupling, nonlocal coupling), though our principal emphasis Lies in the understudied area of nonlocal coupling and its interplay with electronic tunneling; a phase diagram summarizing the latter is presented. The common notion of a "self-trapping transition" is addressed and generalized.