I think you should have a patch kit regardless of whether you have a spare inner tube...for that second flat. This is also why I pretty much turn my nose up on CO2 inflaters. What happens when you get nailed a second time?
Some disposable examination gloves are a great convenience, too, to keep your hands from getting totally roached, since it always seems to be the rear tire that has to be fixed.
Carry a couple of zip ties. Not only do they weigh nothing, that can make the difference between walking and riding should a fastener give way.
Some people swear by the "spoke in a can", that allows you to actually replace a spoke. This is very important if you're running a low spoke count wheel.
The one last thing you could consider but is not essential is a cheap Leatherman-like folding pliers. It can really help with certain repairs and with pulling pieces of wire and glass out of your tire. Put your tools in a plastic bag to reduce corrosion from moisture.
I like carrying one of those screwy littly Ritchey multitools for small adjustments and fixing broken links. Carry a pump, the longer the better. If you have a road bike, carry the largest pump you can put between your bottom bracket and the top tube, the shorter ones just don't work as well. On a mountain bike shorter pumps are OK, since you don't have to get to as high a pressure.
I once went on a ride where I got three flats. After that one, I got slightly heavier kevlar belted tires. Flat problems went away, but I still carry a spare tube and a patch kit. Doing that saved me from walking 15 miles on the three flat trip. Oh yeah, I usually wrap the spare tube in an old sock, probably remnants from the day when any self respecting cyclist rode on sew ups. BTW if people still ride sew ups, carry a spare and a patch kit and make sure you have a needle and thread :).
BTW, with practice you can usually get a tire off and on without having to use tire levers (tire irons in the old days, or maybe aluminums). Usually you need at least one to get it off, but I usually carry a whole set of 3. It is usually better to work the tire onto the rim with your hands with the new or patched tube though.
I got a great comment from my friend Larry. For a whole host of good reasons everyone should carry some form of ID when they ride. It may seem reasonable to carry your ID in your seat pack, but if you get seperated from your bike in the event of a crash (hint: they won't bring your bike in the ambulance with you to the hospital). Larry recommends RoadID which is a dog tag which you wear that has all your pertinent information. Check it out.
Bruce