The FSDO level is not authorized to interpret regulation, and no answer you get at that level will be defensible, even if you receive it in writing. In other words, what you get is purely opinion, and at no time will you ever be able to fall back on that answer.
14 CFR 121.436(a)(3) states that a PIC under Part 121 must have 1000 hours as SIC either: under 121, 135, or 91K. Note that the specific 135 requirement is experience in turbojet multi engine (or multi engine in commuter operations) aircraft of 10 seats or more--in which the PIC must hold an ATP. Likewise, the 91K requirement is specifically multi-engine fixed wing airplane or powered lift operations in which the PIC must hold an ATP. In other words, not just any charter or fractional experience will do. The intent is that it's the equivalent level of responsibility and duty that a Part 121 operation would require.
If you operated for a foreign airline, it wasn't under Title 14 of the United States Code of Federal Regulations, and therefore, not a 91K, 121, or 135 operation.
Time spent as pilot in command or second in command in foreign operations does not apply to the 1000 hr. SIC requirement of 14 CFR 121.436(a)(3).
Note that 121.436(a)(3) doesn't apply if you've served as PIC under Part 121 prior to July 31, 2013.
If your experience wasn't working for a US carrier under 91K, 121, or 135, you may count 500 hours of military experience as PIC in a multi engine turbine aircraft (that requires more than one pilot) toward the 1000 hours required by 121.436(a)(3).
The following FAA Chief Legal Counsel Letters of Interpretation will help clarify the answer to your question and give additional insight. These are defensible and are a reliable source regarding the Administrator's position on your question:
http://www.faa.gov/about/office_org/...rpretation.pdf
http://www.faa.gov/about/office_org/...rpretation.pdf
http://www.faa.gov/about/office_org/...rpretation.pdf
The final letter of interpretation above serves to clarify the specific Part 135 reference requirements of the earlier Kelly letter.