Great idea - I love the notion of providing per-country address forms and save users from having to put up with a convention that does not apply to them.
I agree that it's somewhat uncommon to have the country field that early in an address form - but what about asking the user which country they're from before even starting the address form interaction, i.e. in a separate context? It doesn't need to be a separate page though, just make sure that this field comes before the actual form and is not perceived as part of the form.
One way that springs to mind would be to pose it as a friendly question - use it as an extra opportunity to bond with your customer :-)
BTW: bonus points for providing sensible default values which could be derived from a IP location service or other information from previous interactions, or simply have the five most used countries duplicated (!) to the top of the drop-down list. As a German presented with such a list, I often have to press "G" repeatedly to skip over countries like Gabon or Georgia, and I always wonder how many customers for this particular company come from those places as opposed to Germany...