It's been a while since I've played with iptables, but I believe it's possible to tag packets based on UID. In that case, since apps on Android are assigned unique (for that device) UIDs on installation, it should be straight forward to tailor rules to individual apps.