This sounds like a typical "waterfall" project, rather than an agile one, given your description of the situation. There are two issues here:
- The project is already over budget and behind schedule;
- The customer has requested a change to a key element of the project.
To deal with the first of these, you may need to go back to your contractual arrangements with the customer to determine what you can and can't do to recover the time and / or money. Bear in mind, however, that throwing more resources at a project that is running late is unlikely to have a significant impact if the project was resourced at a reasonable level up front. I would re-estimate the project to deliver the original scope and let the customer decide whether to continue to fund it. It may no longer be viable or deliver the required payback if it is late or costs more than was expected. Only the customer can make that call.
The second issue requires that a project change request be raised, explaining the impact in time and cost to deliver the new requirement. This must be presented to your customer and again, the customer has to decide whether to accept the cost and time impact. Your contract should allow for project changes to be accommodated.
Your customer may have to resolve an internal conflict: whether to go with the original scope and get the project delivered as soon as possible, then do the change as a "phase 2" (if that is even a logical option), versus delivering the project including the expanded scope in even more time and at even higher cost. This may actually require you to create three estimates:
- To deliver the "original" scope, accepting that this may cost more and / or be later than your current plan, without delivering the expanded scope;
- To fix the project and expand it to include the new scope;
- To deliver the new scope as a stand-alone phase after the original phase has been delivered.
Just to emphasise: your approach should be determined with reference to your company's contract with the customer, and decisions should be made by the customer as they are the people who are funding the project, and who have to decide whether it remains viable. Good luck!