After a little back and forth with AWS support, it appears that my situation is the result of a decision on Amazon's part not to "hide" existing Availability Zones even after they are phased out for new instances, since they believed it would be confusing to hide an AZ that might still have running instances. Their recommendation for determining VPC-capable AZs in my situation is either hard-coding or trial-and-error - disappointing, but understandable.
So, my solution of making an intentionally bad request and parsing the error (see below) seems to be the lesser of a handful of evils.
> ec2-create-subnet -c garbage -i 10.0.0.0/24 -z garbage
Client.InvalidParameterValue: Value (garbage) for parameter availabilityZone is invalid. Subnets can currently only be created in the following availability zones: us-east-1c, us-east-1d, us-east-1e.
UPDATE: After some more follow-up with AWS support, I was able to confirm that this is indeed related to my account pre-dating VPC, and that the ability to distinguish between "restricted" and VPC-capable AZs via the API is on their roadmap.