The only kind of pedal I've ever changed is the kind where you unscrew the part right next to the crank (between the crank arm and the pedal). It's a rather narrow space, and the flat head of a pedal wrench just fits into it and grips the pedal axle quite firmly.

The guys at the LBS recommended an extra-long handled pedal wrench, which I'm glad I bought. It takes some serious leverage to get the pedal axle started. My wrench is probably about a foot and a half long.

There is no way I could get a pedal off with just the leverage of a hex key! I salute you for getting one off!!