Yes, 12v to VIN for both should work fine.
Both the 5v (from the Arduino regulator) and the VIN pins are connected to the GSM shield. As best I can read the schematic, if the GSM shield detects 5v on the 5v pin, it will try to use that instead of VIN, and this is when the capacitor comes into play. If you cut (or bend out of the way) the 5V pin from the Arduino to the shield, then the shield will be forced to use VIN. At that point we have exactly what you propose: 12v to both devices in parallel, and each device will use its own on-board regulator.
I'm not the expert on this stuff so I hope others will confirm but this seems correct to me.
I agree with you Alek, Arduino really needs to put a note about this issue on the wiki page.