A chess variant puzzle

Consider the rules of chess modified so that the objective is to capture the opposing king. (I once played someone who apparently thought this was the objective, which was my inspiration for this.) The rest of the game remains the same, except that it is now legal to move into check—otherwise capturing the king is impossible, since checkmate would be followed by stalemate.

At first glance one might think the game is identical so long as one takes care to never move into check if at all possible. In fact, the game has appreciably changed since forcing a stalemate is harder when one has additional legal moves.

The puzzle is this: is stalemate even possible now? Why or why not?