Here's a nicely organized collection of games that one can play with only pencil and paper. Really handy to learn a couple of these for entertaining kids on the fly.
I also found this interesting tic-tac-toe variation, ultimate tic-tac-toe:
...which has a smaller board inside each square of a larger one. The kicker is, you must make your move on the small board corresponding to your opponents last move.