This happened to my husband once. Taking something flat and pushing it against the bottom of the pedal should spread the cleat wings from the underside and release your shoe. It might be easier if you take the pedal off of the bike.

He also just had the idea that you might be able to clip your other shoe into the bottom side of the pedal and then when you release that cleat (have someone hold onto the stuck shoe) you should be able to pull the other shoe out at the same time.