There just is no way around it, the only way to be secure is use SSL to share secrets when you register. From then on you can just transmit an authenticator (stored in a secure cookie) comprised of an expiration timestamp, any identifying user data (like userID), and a non-malleable MAC digest of the expiration and userID. Doesn't protect against replay but it helps to enforce a short expiration for the authenticator. With this approach you'll only need to use SSL for the initial login.
This is the best explanation of web authentication I've encountered on the net [PDF]: