Using an Agile approach while contrained by traditional contracts and customer attitudes can be very challenging.
However, there are many aspects of Agile that should still be of value:
Transparency
Even when working with fixed scope and deadlines it is worth using the approach of incremental delivery. This helps to reduce risk and will build up trust between you and your clients.
Engineering Practices
Many Agile engineering practices (such as those used in XP) can be used even in traditional projects.
Look to leverage the value of pair programming, continuous integration and automated regression testing.
Teams
Agile teams work well because they are empowered and self-organising. Try to keep your teams together as much as possible, even spanning over several projects. This will help the teams to learn how to work together and to gain benefits from inspecting and adapting their approach.
Communication
Emphasise the importance of communication:
- Daily stand-up meetings with just the core team members (for synchronisation, not as progress reports)
- Information radiators such as physical task boards or visible product backlogs
- Work closely with the customer to ensure you fully understand their requirements, perhaps have them co-locate with the team
And then...
Build up a relationship of trust with your clients by working closely with them and delivering value frequently.
Over time you may find that your clients are more willing to be flexible about their contracts and the nature of their engagement with your organisation.
As an example, some organisations like to form joint teams consisting of in-house and outsourced people. These mixed teams create a lot of trust and they may then consider a time and materials based contract rather than insisting on fixed price contracts.
Finally, there are a growing number of Agile contracts around. I suspect that you need to have a strong relationship with a client before they would be willing to accept such a contract, but it is possible.