Create fields for all the main address components, including postal/zip codes, but don't make them mandatory or put restrictions on format.
People who are used to always including postal/zip codes will include it when they see the spot on the form. If this is a shipping address, and they actually want to receive their purchase, they are motivated to include the information!
In contrast, if they were just signing up for a web service, and you started asking for a full mailing address without explaining why they should give it to you, then people would be more likely to leave it off.
Your other options are:
Create a database of all countries you might be shipping to, and which address fields are required for each, and adjust your form validation accordingly. This is what most major e-commerce sites do, but I think this is the "complex solution" that you didn't want to code.
Make all fields required, and frustrate potential customers by telling them "postal code is required" when they don't have a postal code to enter. Not a good plan.
Use a completely open-ended address field (Address line 1, Address line 2, etc.) and trust that people will know what is appropriate for their country. However, without prompting people to remember the different types of information, they are more likely to leave it out.