You could avoid the current Firesheep via some "security thru obscurity" scheme involving authentication via dynamic session management as discussed here. You can use "Digest Authentication" (RFC 2617), but that is still vulnerable to a MITM attack, degrades the user experience and requires the server to store your password (or a password equivalent) in the clear.
But avoiding SSL/TLS would not get around the two fundamental problems that without encryption: (1) all the private content is shared in the open, and (2) a determined attacker could figure your scheme out and defeat it.
See some cute examples of active attacks, mythbusting about performance penalties, and specific advice on deploying SSL from EFF: How to Deploy HTTPS Correctly. Note also the Stack Overflow meta discussion on why it hasn't been fixed on Stack Overflow (yet).
Note that the exposure for common sites is worse than I initially thought. E.g. note this wrinkle as the Firesheep author explains in a great post
You can’t simply avoid visiting the
sites that are being attacked here.
There’s an enormous amount of mixed
content on the web today, such as the
Facebook “Like” button, Digg’s “Digg
It” button, twitter widgets, and even
embedded images that are hosted on
Flickr or other photo sharing sites.
Every time you access any web page
that includes any of this content,
your browser also sends any
authentication cookies you have with
the request to pull down the widget.
You can at least fix the errors he discusses there (like actually invalidating session cookies when a user logs out!!).
You can also advise your users on how to protect themselves to some degree from these "sidejacking" attacks, e.g. to use a VPN or find a WPA2 wifi network (but see WPA2 issues here).
Thanks to @D.W. for a link to the best-thought-out interim approach I've seen: SessionLock Lite by Ben Adida. It at least prevents persistent hijacks by passive attackers: Benlog » keep your hands off my session cookies. Just don't stop there - engineer an SSL deployment....