I live in one of those countries and I think people are over-analysing the problem. I think you're perfectly safe with:
Addr 1 (req)
Addr 2 (optional)
State (req but including "Outside US")
Post/Zip Code (optional outside US)
When I order stuff from the US I just put my city and state in the Addr 2 line.
In the end this is a classic example of the "perfect being the enemy of the good". Look at where your sales are going and allocate validation efforts accordingly. A lot of sites include Canadian provinces in the "state" field for example.