There's a great article by Jason Rohrer in the Escapist, called Testing the Limits of Single Player. In it, he explores possible games that have deep game play, setting himself the following limits:
Can you make an AI-free, randomness-free, physical-challenge-free, single-player game with gameplay depth akin to that of Go?Interestingly enough, his solution i45hg is modelled in part on Conway's Game of Life, which is a no-player game that has the above properties. This suggests at least one way around the problem, which is to design a Turing complete interactive game system and let the player explore that.
I can describe another such game, which involves preventing the player explore any previous path. At least, I can't describe the game, but assume that at each stage, there are enough different choices so that the combination of possible sequential choices grows big very quickly. You could design a game this way, which has victory conditions that can be met in a single game, but the player is restricted from ever repeating those victory conditions again. Provided the ratio of victory conditions to non-winning moves is sufficiently low, you'd end up with a game that could remain infinitely replayable without being random.