The solution at http://www.xbox360achievements.org/game/xevious/guide/
provides a good hint, and full credit to Sajaa and litepink for that. However, it's a little short on detail and there are some improvements to make this easier.
You can get this achievement "naturally" by just getting far enough in the game. However, expect to have to get farther than the second Andor Genesis, starting from the beginning of the game, to do this. This is going to be quite a challenge for many players.
The best way to make this easier is to kill as many air enemies in the very first stage as possible. The ground enemies in the first stage are very passive and can normally be ignored completely. You might get a single shot fired from the ground in the first part of the first stage, and usually not even that. Therefore, the basic tactic is to kill air enemies, ignoring everything on the ground, until just before the checkpoint, kill yourself, and repeat until you're down to your last life. Then play through the game as far as possible and hope that's enough.
Two key ways to make this easier: First, go into the game options and change the extra life option to 10,000 and every 40,000. This does not affect the achievements, only eligibility for leaderboards. Second, there is a Sol Citadel just before the checkpoint, which you can reveal each time for a significant number of points. Even if you only reveal it and don't destroy it, this will be enough points to earn you an extra life while still on the first level, giving you four runs through the first level instead of three. Look at the image at:http://strategywiki.org/wiki/Xevious/Walkthrough#Sol_Tower_l...
Be sure that you kill yourself at that citadel or just after. If you get past the jeeps, you've gone too far and you'll restart on the second level. Other guides say that the checkpoint is the second river, but you'll hit the checkpoint just before the second river appears at the very top of the screen.
Other guides say to try to collect special flags to extend your playthrough. I wouldn't bother. The difficulty of air enemies is going to be fairly high given how many you're killing, and Special Flags are extremely difficult to locate, so you'll probably just get yourself killed. You'll also miss a bunch of air enemies while you're concentrating on getting the Special Flag. Just focus on killing air enemies, bomb things when they'll otherwise kill you or when there are no air enemies, and practice so that you can get as far as you can. Don't panic if you mess up and pass the checkpoint on your third time through the first level; I did that and still unlocked this achievement by getting to level 9 in that playthrough.
The air enemies come in a well-defined order, which you can use to guess at how far you've gotten towards killing 500 (since they increase in difficulty as you kill more enemies). See:http://strategywiki.org/wiki/Xevious/Getting_Started#Air_ene...
for the list of air enemies and their pictures. The rough order in which they'll appear is (from memory; leave a comment and I'll fix if I misremembered some of the order):
3. Toroids that shoot
4. More Torkan
5. Gido Spario
8. Zakato that move in straight lines
9. Jara and Torkan together
10. Zakato that move at angles
What this means is that once Tarrazi start showing up, you're almost there. If you haven't seen any Terrazi, you've probably not killed enough air enemies to have a shot at this achievement. (Note that the air enemies near an Andor Genesis, and at a few other places in the game, are fixed and won't vary by how many enemies you've killed.) Enemies will drop back a few levels of difficulty when you die.
It's okay to die a bit into the level as long as you didn't hit the checkpoint; you'll get another pass at the air enemies with a lower difficulty, which can be great. Just try not to die on the levels with the spinning indestructible shields, since they have very few air enemies.
One final hint: when you get swarmed by Gido Spario (the fast-moving bullets that angle across the screen), try to stay in the center of the screen, since they're one of the best opportunities for racking up lots of kills but you'll miss them all if you let them push you up the sides of the screen away from them. Also, except when killing groups of Toroids or Jara, don't shoot too fast
. You can only have three bullets on the screen at once, and you'll miss a bunch of air enemies if you expend them all into empty space.