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
If you have been able to give a quote on a project with an exact final date on all the features, why did you switch to an agile approach? You and everyone else struggles with this and an agile approach is being up front with this fact. Use it as propaganda against the competition. Southwest Airline doesn't promise you an isle seat like everyone else who does and then gives it to someone else.
Of course the client wants an exact ending date. They want inexpensive, bug-free software delivered ahead of time regardless of any changes to the original request. Tell you sales team to learn how to sell a project using agile principles. The more interations you go through the closer you can get to knowing when the project will be finished. The client also learns to factor the effects of change requests.