I'll note that there are a number of worked examples which allow GPL'ed code to be distibuted via an app store already. All you have to do is use a two step process. So the app-store distributed application (for example, the Android Better Terminal application) can simply download the necessary GPL'ed or LGPL'ed components from a web site, which can respect the source code distribution requirements.
There are issues around what is one program versus multiple programs/"mere aggregation" (i.e., does a Copyleft license infect across a shell script invocation, remote procedure call, or a pipe), but those are issues which exist already.
I'm not sure off-hand whether or not IOS applications are able to download executable content, but this is certainly possible on Android devices.
- Ted