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