Alternatives:-
bmx style pedals with the little pins all over them - better platform than a cage and better grip
shoes with a better sole - Fiveten do some great ones with soles that truly grip.
CRC do the Impact version, read the reviews here:-
http://www.chainreactioncycles.com/Models.aspx?ModelID=18195
there are lots of other options with good soles and the larger platform of the bmx pedal means that super stiff soles aren't as vital.
toeclips with or without straps - these don't seem to fit BMX pedals so you'd need to stick with cages. Strapless are easier but less secure, straps are more secure but more faff. Many people find the plain strapless ones are more than adequate for their needs.
Powergrips - work with cage pedals and are diagonal band across pedal. foot is inserted at an angle and the strap tightens as you straighten your foot. The fittings aren't the strongest and adjusting length for different shoes requires use of an allen key.
Webbing and velcro straps - these are becoming very popular, same idea as the powergrip but they fit bmx style pedals and run straight across pedal rather than diagonally. Idea being that you can adjust these via velcro tab for whatever shoe you're wearing. Expensive and hard to get hold of right now, but this site shoes most of what's on offer, even a place that shows you how to make your own:-
http://www.pedalconsumption.com/files/tag-toe-straps.html
the prices will be coming down and availability going up very rapidly by the look of things.
All of these options have the benefit of your bike being rideable with any shoes. Most of these options make falling off, clipless style, less likely.