Shoe Method
One way to loosen the corkscrew is to remove your shoe, place the bottom of the bottle in the foot hole (to protect the glass), and then bang the shoe against a stone wall repeatedly until the cork eases out of the bottle. This video provides a good demonstration. Just be sure to remove the capsule before trying.
This woman adapted this method using a book instead of a shoe.
House Key Method
You can also remove the cork with a house or car key. Select one of your house keys and insert it into the cork at a 45-degree angle. Keep pushing the key until most of it is inserted into the cork. Then twist the cork around a couple times and pull up as you do, gradually coaxing the cork out of the bottle.