Is it possible to have GPL software in the Mac App Store?
If you mean taking software that you do not hold copyright to, and which you are only allowed to use and copy because it was licensed under the GNU GPL, then no.

The FSF spells it out here: section 6 of the GPL says "You may not impose any further restrictions on the recipients' exercise of the rights granted herein", and the Mac App Store Terms of Service explicitly add other restrictions.

The Software Freedom Law Center's legal representative confirmed this: the App Store agreements, on all platforms, are incompatible with the GNU GPL.

Apple seems to be disallowing GPL programs in the App Store as a matter of policy, but if you managed to sneak one through, then the author of the program could go after you for violating their copyright.

A completely different case is where you hold the copyright to a piece of software.  In that case, you are welcome to distribute it under more than one license.  (For example, Firefox was for a while licensed under the MPL, GPL, and LGPL.  MySQL is licensed under the GPL and also a proprietary license.)  So if you sell a program through the Mac App Store, you can also release it under the GPL -- assuming you are allowed to do each of these things independently.

(If you wanted to use somebody else's GNU GPL-licensed code in one of the App Stores, you could write to the copyright holder and see if they're willing to sell you an alternative license to their software.  They're under absolutely no obligation to do this, of course.)

VLC ran into trouble (I think) because copyright for the software was held by many different people, and the whole program was only allowed to be distributed under the GPL.  Some programs sidestep such issues by requiring contributors to assign copyright to them, but most don't.