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 main idea behind the agile methods is to help you be productive - in a positive sense. No one cares if you spend an hour surfing every day if you meet the deadline. Everyone gets mad if you surf half an hour every day but miss your deadline. The solution: Make it easier for you to meet the deadline.
As you noticed, pair programming makes sure you stay focused (among all the other advantages like improving skill/knowledge spreading, better code, less bugs, uniform design, etc.).
I found that discipline is always a struggle for me. If I pair with someone, chances are that one of us wants some work done today and pulls the other along. So the "work for a month" often becomes turns into "work together for one week", being surprised how that huge amount of work resolved in the end, spend a day or so recovering (refactoring, fixing TODOs in the code, adding a couple of tests, surfing with a clear conscience) and then grabbing the next month of work.
Net result: I'm much more relaxed (more because than despite the constant supervision), team cohesion is much better, work gets done more quickly, people don't hang around some minor issue for hours or even days (because someone else can spot the problem much faster).
When you say "you may actually feel ashamed", isn't that a good thing? It means you feel that you did wrong and you should. You're not getting paid to get nothing done. Not getting anything done makes you feel helpless, unhappy, unworthy, miserable. Instead of feeling ashamed, stand back and think "Why didn't I accomplish anything today?" Do you need help? Is there something you don't understand? Is the current task too hard? You don't like it? Maybe you can switch the task with someone else. Maybe someone else can help you get through. Agile means: Assume responsibility instead of being micro-managed like a puppet on strings. You need a tool? Go to your boss and ask for it. Learn to argue. Learn to stand up and shout when you have to.
As for tests, there is a sweet spot when your code suddenly collapses from "nice" to "perfect". That's the moment when you notice that you need to implement feature X and you thought that will be a nightmare and suddenly realize that the code is almost there. Just a small refactoring here and there. A new class and done. Four weeks of work suddenly became a day. Victory! Triumph!