It's not just the US based mailing address for registration or US based credit-card or bank account: even if you had all these, like I do, you will find that these online filing companies do not have the infrastructure to handle non-resident taxes.
The reason why the popular online filing companies do not handle non-resident taxes is because:
Non-residents require a different set of forms to fill out - usually postfixed NR - like the 1040-NR.
These forms have different rules and templates that do not follow the usual resident forms. This would require non-trivial programming done by these vendors
All the NR forms have detailed instructions and separate set of non-resident guides that has enough information for a smart person to figure out what needs to be done. For example, check out Publication 519 (2011), U.S. Tax Guide for Aliens.
As a result, by reading these most non-residents (or their accountants) seem to figure out how the taxes need to be filed.
For the remaining others, the numbers perhaps are not significant enough to justify the non-trivial programming that need to be done by these vendors to incorporate the non-resident forms.
This was my understanding when I did research into tax filing software.
However, if you or anyone else do end up finding tax filing software that does allow non-resident forms, I wil be extremely happy to learn about them.
To answer your question: you need to do it yourself or get it done by someone who knows non-resident taxes.
Some people on this forum, including me for gratis, would be glad to check your work once you are done with it as long as you relieve us of any liability.