I think the first thing to realize is that there is a difference between being Agile and being agile. Slowly rolling out agile techniques and characteristics - cross-functional teams, adaptive planning, evolutionary/incremental delivery, time-boxed iterations, and even introducing concepts from Lean are very different than introducing Extreme Programming, Scrum, or Crystal.
You explicitly mention customer involvement. Yes, many of the Agile methodologies call for customer involvement, but that's not required to be agile. In every government/defense related program, I've always had a program or project manager who was the point of contact with the customer. This person becomes the "voice of the customer". It might be slowed down as they teleconference or email or call and clarify, but you can have a single person (or a group, if you have deputy PMs as well) that is the customer representative of your team. Admittedly, it's not quite the same. But isn't being agile about being flexible and responding to change?
You also mention a few key concepts: predefined requirements, having feature requests "thrown over the wall", a lack of prioritization because "they are all important", and fixed-cost and/or fixed-schedule projects. Each of these can be addressed in different ways.
If you think you have all of your requirements up front, chances are you don't. Requirements do change. Just because you have a "finished and signed off" specification doesn't mean it is set in stone. Given whatever requirements document you have, capture them how you feel comfortable and/or in the manner specified by the contract and deliver the requirements, the design, and the architecture. In addition, see if you can treat these are living documents (a design document I saw today at work is labeled as Revision G, which means it's on it's 8th update). Ask about how much you can leave as TBD in any given iteration and how much needs to be firmed up now - there might be some give and take.
Be agile with your documentation. Don't duplicate efforts between "what your team wants" and "what the customer wants". For example, if your customer wants a traditional software requirements specification and your team wants to use user stories, try to adapt to a traditional SRS and use action items and a rolling action item list instead of user stories so that you don't spend time formulating both "the system shall..." and " must be able to because ". This does take discipline on the part of the team, though, to adapt to differences between projects. Capture problems in reflections.
Once you get to development, you might run 5 or 6 iterations, and then invite your customer to your facility to see a subset of your implementation. Rinse and repeat this process. It's not the constant involvement demanded by some methodologies, but you do have the advantage of high visibility. If your customer says no, at least you tried. If they say yes, you can enlighten them on being agile. On one project I was on, the customer visited the site every few months (3-5 months, usually). They would watch us go through QA testing, they would discuss concerns with engineers, and business with the program/project office. It was an opportunity for everyone to get on the same page.
Testing and maintenance happen the same as on other agile project. Create your test procedures and document defects in the appropriate way, track metrics per contractual obligations, and document test results. If you want to follow TDD, go for it. Continuous integration is another good idea. During project status meetings, your project manager can use this information to say "we implemented N requirements, have M tests, X tests pass" and update on project health and status to the people with the money.
Speaking of money, we have the fixed-cost and/or fixed-schedule problem.
Dealing with a fixed schedule is fairly straightforward. Given your requirements, you know how many iterations that you can complete. Your workload for each iteration is pretty much set in stone in terms of features to implement, test, and integrate. It might be difficult, but it's not impossible to break up features and assign them to iterations in advance. This goes back to my point about inviting the customer - if you have one year and are using 2 week iterations, perhaps invite the customer quarterly (and invite them every quarter) and show them the results of the previous work. Let them see your prioritization of requirements, your future plans, and how you are going about scheduling.
Dealing with a fixed budget is similar. You know how much time you have, how many resources you have for the project, how much they cost, and therefore how many hours everyone can work per iteration. It's just a matter of ensuring that everyone keeps track of this carefully. If your company can eat the cost of overtime, go for it. Otherwise, make sure everyone works the appropriate length of time and use good time management skills and time-boxing to keep everyone productive. More productive hours is what you need to keep costs down - deliver more value-adding documents and software without the cost of meetings and overhead.
Ultimately, it's not about necessarily being Agile, but applying the things that make Agile good and being agile. Be able to respond to changes in requirements, be able to deliver frequent software even if the customer doesn't want it, only produce value-adding documentation (along with whatever you are contractually obligated to produce), and so on.
Best Answer
The key to doing this well is by use of a support contract.
Basically, when you first sell the client, you sell them based of your expertise, and you do it waterfall. That means a contract that sets the scope and a firm dead line. This is what the client wants. The client more or less knows the scope. Waterfall works very well, in a fixed & defined scope environment, I would say it works better than agile in such environments. And in this case it gives the client a level of comfort when the tendency is to be nervous because he has never worked with you before. That’s Ok, Agile is not always better then waterfall.
So you have a fixed price contract for X scope. Then you tell the client “Look, you are going to want to make changes, and you are going to need us to support you post production, let’s set aside 20% of your budget for these things to be used on an as need basis by means of a support contract.”
Should a change come up during the project, simply defer it to be handled under the support contact. (Assuming this change would cause a serious disruption to the project)
The terms of the support contact are as follows “Work to be done on a per hour basis, as requested by the client, can be used for change requests or general system support and maintenance.” BAM! You are in Agile.
You can then continue to extend the support contact, and simply use the support contact as the means to run new projects. Additionally if these hours are purchased and paid for upfront, we usually give the client a 15% discount. It's Win-Win.