We prove a shape theorem and derive a variational formula for the limiting quenched Lyapunov exponent and the Green's function of random walk in a random potential on a square lattice of arbitrary dimension and with an arbitrary finite set of steps. The potential is a function of a stationary environment and the step of the walk. This potential is subject to a moment assumption whose strictness is tied to the mixing of the environment. Our setting includes directed and undirected polymers, random walk in static and dynamic random environment, and, when the temperature is taken to zero, our results also give a shape theorem and a variational formula for the time constant of both site and edge directed last-passage percolation and standard first-passage percolation.