This question has two levels:
- actual problem of contracting the work for agile team
- does it really matter how the work is contracted?
It actually doesn't matter how the contract looks
Even if you sign fixed scope/price contract with customer you still might be better off using agile/iterative approach.
Use it as risk minimizing factor.
Nothing stops you from using e.g Scrum for fixed scope bid:
You can work in iterations
You can deliver increments of working software every Sprint
You can incorporate clients feedback (it might cause change/request, formal scope adjustment)
But what is more important, in the situation you run behind and you have problems with delivering 100% of scope on time/budget (which happens in most of software projects anyway)... you will be better off with agile approach.
You have better negotiation position with your customer:
Most importantly, you will have big part of the scope done and potentially shippable
Customer has probably seen your progress, so there is much more confidence and trust if your ability to eventually deliver, therefore it will be easier to find common ground
Best contract for agile team
Most commonly used contract is Time & Material where customer pays for your team's work.
I've seen interested variation of agile contract that was proposed by Ken Schwaber in one of his books (I think Agile Project Management with Scrum):
After initial Release Planning you agree on the scope and contract value
If all the work is done and under budget you get 10% bonus added (not sure about exact figure)
Customer can decide to stop the work after each Sprint and pay you 20% of remaining budget as a re-compensate for the fact that you need to instantly reassign team to other teams
If you go over budget then customer is paying you much lower rate for the rest of work (you're sharing the risk of going over).
How it all ties together
I usually approached your situation initially without even proposing anything else than fixed price contract as it seemed to be lost battle without relationship and trust. To build this relationship? Proving that you're professional and you know what you're doing is the best way :)
Upon contract signing I would inform customer that you'll be using Scrum for this project and invite them to participate. This is crucial, you want them to see for themselves how "their" software is built, you want then to have influence and see they can realize business value faster. If client stakeholders have real need for the software and you will engage them, there is good chance they will get addicted to the approach.
After first project, you can try agile contract described above or move strictly to time & material. It's matter of preference and business circumstances on both client and your company.