manphotoさん、こんにちは。
私もMac経験が浅く、悪戦苦闘しながら、なんとかアプリを無事公開できました。
私のやり方でよければ、試してみてください。
（2013.11.10 Mac OS X 10.8.5使用 FlashCC AIR 3.9.0.1030 Beta）
まず、
今回の事象ですが「AIR 3.9.0.1030」でも解決されていないと思います。
私はその後「AIR 3.9.0.1200 Beta」でパブリッシュして試しましたがダメでした。
ちなみに、AIR Beta版が下のサイトにあります。
http://labs.adobe.com/downloads/air.html
今みると、「AIR 4 Beta」になっていますね。。。
これを入れたら案外、解決できるかも…（ただ、Beta版なので自己責任になりますが）。
それと、
私の場合は「Non-PIE Binary」の問題はありませんでした。
では、本題に入ります、が、
結構な長文になってしまいました。既にご存知のこともあるかと思いますが、ご容赦ください。
それでは、よろしくお願いいたします。
全体の流れ
1、Flashでアプリをパブリッシュ
2、下準備・アプリファイルを解凍
3、アプリの署名を表示・取得
4、署名を削除
5、アイコン画像ファイルを加える
6、アイコン画像ファイル名をinfo.plistに加える
7、再署名
8、アプリファイルを圧縮
9、Application Loaderで送信
以下の説明で使うアプリ
アプリ名：おためし
ipaファイル：otameshi.ipa
1、Flashでアプリをパブリッシュ
まず、Flashでアプリを、デプロイタイプ「Apple App Store」でパブリッシュ。
このとき、「パブリッシュ」ボタンを押す前に、2つのファイルを加えます。
Default-568h@2x.png <- 4インチ画面用アプリ起動画面（640x1136の画像ファイル）
Default@2x.png <- 3.5インチ画面用アプリ起動画面（640x960の画像ファイル）
画像の内容は何でもよいかと思います（私は「Loding」という画像にしました）。
これらのファイルを入れておかないと、署名できてもApplication Loaderではじかれます。
さて、ipaファイルができました。
ここではipaファイルを仮に「otameshi.ipa」とします。
2、下準備・アプリファイルを解凍
そして、ターミナルを使いやすくするため、下準備をします。
デスクトップにフォルダを作ります（半角英数字の方がいいでしょう）。
この名前のフォルダを仮に「ver100」とします。
このフォルダ「ver100」にアプリ「otameshi.ipa」ファイルをコピーします。
「otameshi.ipa」を右クリック -> 名前の変更で拡張子を「ipa」から「zip」へ変更します。
「otameshi.zip」をダブルクリックで解凍すると「Payload」というフォルダができます。
ここで「otameshi.zip」は削除しましょう（「Payload」を後で再度zip化するときに邪魔になるので）。
「Payload」フォルダをの中に、侵入禁止マークアイコンつきのファイルがあります。
ここではそのファイルを「おためし」とします。
「おためし」を右クリック -> パッケージの内容を表示 をクリック ->内容が表示されます。
ここで、後の作業でこんがらないように、「Finder」をもう一つ出します。
これには「ver100」フォルダの中身を表示させます。
そして、さらにもう一つ、iOS7用のアイコンがある場所を「Finder」で表示させます。
これで、「Finder」が画面上に3つあることになります。
アイコンは3つ作っておきます（iPhone用アプリのみなら1つでいいのですが折角なのでiPad用も作りましょう）。
Icon-60@2x.png <- iPhone用（120x120サイズ）
Icon-76.png <- iPad用（76x76サイズ）
Icon-76@2x.png <- iPad用（152x152サイズ）
それでは、ターミナルを起動します。
まずはディレクトリを移動します。「cd ディレクトリ名」で移動できます。
デスクトップに移動したいので、
cd Desktop
と入力してreturnキーを押してください（大文字小文字に注意してください）。
カーソルの左側に、Desktopの文字が出てきたかと思います。
そして、さらに、
cd ver100
と入力してreturnキーを押下。
これでフォルダ「ver100」の中に移動したことになります。
3、アプリの署名を表示・取得
そして、下のコードを入力（もちろんコピペでOK。ファイル名は変えてくださいね）。
私はテキストファイルによく使うコードを貼付けて保存しています。
codesign -d --entitlements - PayLoad/おためし.app
そうすると、数行にわたって文字が表示されます。
「??qqm<?xml version="1.0"〜」の「<?xml」のはじめから
「〜</plist>〜」の「</plist>」の終わりまで選択コピー。
テキストエディットを起動。
メニューバーの「フォーマット」を選び、「標準テキスト」を選びます。
テキストエディットにペースト。下の名前で保存。保存場所は「ver100」直下にしてください。
「entitlements.plist」
4、署名を削除
そして、以下のコードで署名を外します。
rm -r "Payload/おためし.app/_CodeSignature" "おためし.app/CodeResources" 2> /dev/null | true
パッケージの内容が表示されている「Finder」から「_CodeSignature」が削除されます。
5、アイコン画像ファイルを加える
署名削除後、Icon画像ファイルを3つ、パッケージの内容が表示されている「Finder」へコピーします（「おためし」直下にコピーしないとダメ）。
6、アイコン画像ファイル名をinfo.plistに加える
「Info.plist」をダブルクリックで開きます。
そのファイルを開くと、「Icon files」と書かれた行があります。そこをクリックすると、
「+」「-」のマークが出ますので、「+」を押して、加えたアイコンのファイル名を一つずつ追加してください。
Icon-76@2x.png、Icon-76.png、Icon-60@2x.pngの順で追加するとすっきりします。
赤xで「info.plist」を閉じます（追加したとき既に保存は完了します）。
アイコン画像ファイルがある階層（「おためし」直下）に、
Default-568h@2x.png、Default@2x.png
があるか確認してください。なければ、アイコン画像ファイルと同じように「おためし」直下に移動かコピーしてください。
7、再署名
これらの作業が終わりましたら、再署名です。
ただ、私の環境の場合、このまま署名するとエラーになってしまいました。
（ちなみに私は、Mountain Lion 10.8.5を使っています）
なので、再署名前に下のコマンドを実行してください。これは、私の「自己解決しました〜」で書いた内容と一緒です。
export CODESIGN_ALLOCATE="/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/codesign_allocate"
大事なのは、ファイル「codesign_allocate」のパスを入力してあげることです。
人によってはこのファイルの場所が異なってくるので、パスを確認してください。
確認方法は、Finder -> アプリケーション -> Xcode -> パッケージの内容を表示から見つけてください。
見つけたら、右クルック ->情報を見る でパスが表示されるのでコピペするなりして、上のコードを変えて実行してください。
そして、再署名します。下のコードを実行してください。
codesign -f -v -s "iPhone Distribution: たぶんあなたの名前か任意の名前 (配布用証明書番号)" --resource-rules Payload/おためし.app/ResourceRules.plist --entitlements entitlements.plist Payload/おためし.app
コードの中に最初の方で取得・作成した「entitlements.plist」があることに気づかれたと思います。
そして、コードにある「たぶんあなたの名前か任意の名前（配布用証明書番号）」という所に入れる文字ですが、
「キーチェーンアクセス」から証明書をダブルクリックすると確認できます。
配布用証明書の名前と番号に書き換えてください。
コードを実行するとパスワードを求められるかと思います。パスワードを入力して先へ進んでください。
パスワードを求められれば、ほぼ再署名成功と思ってよいでしょう。
パッケージの内容が表示されている「Finder」には、フォルダ「_CodeSignature」が再び現れたかと思います。
そして、再度、一番最初に実行したコード、
codesign -d --entitlements - PayLoad/おためし.app
を実行してみましょう。最初に実行したときと同じ文字がでてきたでしょうか？
そうであれば署名成功です。
ターミナルを使うのはここまでです。
8、アプリファイルを圧縮
「ver100」の中身が表示されている「Finder」に戻ります。
「Payload」を右クリック、圧縮します。
「Payload.zip」になってしまっているので、名前と拡張子を「otameshi.ipa」に変更します。
これで作業は終了です。
署名後、ファイル内容をいじったら駄目ですよ〜。
9、Application Loaderで送信
Application Laoderでこのipaファイルを送信してみましょう。
最後の注意点ですが、デスクトップ -> ver100 の中にあるipaファイルを送信してください。
私は変更前のコピー元のファイルを送ってしまい「アレ？」となってしまいました。笑
