Creating an AIR Badge would be a good option.
The idea is you pass a link to the client, the AIR Badge check if
AIR is installed. If it is, installs your app, otherwise installs AIR
first.
There's a pretty good AIR Badger tutorial on the Adobe Developer Connection site. AIR Badger is an AIR App Grant Skinner wrote to make the setup easier.
Also check out the new AIR Launchpad, which is another AIR app that helps you get started with all sort of AIR related functions, including install badge.
Unfortunately the AIR Badger works online.
You cannot bypass AIR install. Maybe have a third party utility(batch script/etc.) that looks for air related files/.air filetype associations and based on that launches an AIR installer you supply on CD or the app itself.
On osx you have the mdls command that displays information about a file. You could check for kMDItemKind
:
mdls -name kMDItemKind /path/to/yourApp.air
If it prints "com.adobe.air.InstallerPackage", then air should be installed, otherwise it will just print "Document".
There should be something similar for windows command prompt that checks registry file type associations.
After you've done that check, install AIR first or just the app, depending on the result.
HTH