Companies that are entirely foreign-owned are perfectly legal. You do not need a US-based partner.
But if you're not a US-citizen and want to create a company in the US, I would highly recommend NOT forming it in California, for cost/paperwork reasons. There are many other US states that are much more business-friendly to choose from.
(IANAL disclaimer) Merely having customers in California does not create a "locus of business" in CA that would require you to pay the $800 annual fee. On the other hand, if you have an office and/or employees in CA, it probably would.
Billing clients in California can create a nexus but it depends on the amount of sales. A company is considered doing business and subject to California tax laws if state sales or property exceed the following amounts:
* CA sales of $601,967 or 25% of total sales.
* CA real and tangible personal property worth $60,197 or 25% of total property.
Also, if a company engages in any transaction for the purpose of financial gain within California, the Franchise Tax Board considers that doing business within the state. An example would be meeting potential clients during a professional conference and negotiating a sale. This can be done by either a member of the LLC, an employee, or an agent such as an independent contractor.
I assume you'd need a US-based partner in the LLC.