Go find/buy two sets of Stackable Headers (yes two) like these and also go get 28 (2x8 + 2x6 = 28) micro hard drive jumpers like this pack of 24 ... unfortunately you'll need 2 packs to get to 28 ... but they aren't real expensive. Now take the two sets of Headers and make a set of 4 pairs and put a micro jumper on each pin of the pair of headers. Now, when you want to access the Arduino headers with a shield that doesn't have headers of it's own: first, place your new special headers into the Arduino header with one of each pair on the outside of the Arduino Header (so you will see the pins of the header that doesn't go into the Arduino on the outside of the Arduino Header, away from the board) and finally, place the shield so it is sitting on the special headers; again, so the extra header in the pairs is on the outside.
Now just run whatever connections you need to the outside pair, the micro hard drive jumpers will make the connection to the Arduino for you. NO SOLDERING REQUIRED.
Here's a sample picture of an Adafruit Wave Shield sitting on a Mega 2560 with wires runnnig from pins 10, 11, 12 & 13 to 53, 51, 50 & 52 respectively (so the shield will work on the Mega) using the special headers:
A couple of things to remember:
1. You can't add another shield on top ... but, if you don't need to, this works well.
2. If the top shield requires connection to the ICSP pins you probably won't have to do this since, in reality, what we're doing here is connecting pins from the shield to the mega that are supported through the ICSP pins. In-fact, I'd almost guess that if the shield has an ICSP connection and it doesn't work as-is on the Mega, the above won't help either.