I've read that they seem to work "too" well on large samples and reject even the smallest deviation.
This sort of (misplaced) sentiment is common, but it arises from people misusing the tests. They are misusing them at all sample sizes, it's just more obvious at large ones. It's particularly a problem with goodness of fit tests, but it's also common with many other kinds of tests.
Hypothesis tests are (almost always) deliberately designed to be consistent, that is, to reject all false nulls as $n$ goes to infinity; indeed it's what people demand of their tests.
The problem is that people choose to state an exact equality null (and use a test for that exact equality null) when that's not actually what they want to test for; otherwise they would have no complaint when the test quite reasonably rejects a small deviation from the model in a large sample. It's like complaining that a hammer is just a bad tool when you've been using it to bang screws in. The problem in that scenario is not with the hammer; it's often a useful tool when used for the task it has been designed to carry out.
Your actual problem is not "are these two distributions* exactly equal?" so why use a test that will try very hard to tell you whenever they aren't?
It seems like you want to know whether an exponential model would be adequate for some purpose ... and in that case you would need to consider the situation in relation to its impact on the properties of that purpose. Each such impact is more like a question of effect-size, not significance.
You have not stated the purpose that I can see so there's little more to be done, except to talk in generalities.
Proof that the exponential distribution can be used for the data
That depends on what you're using the data to do, on what properties of that thing you care about, and how sensitive you are to deviations in those property (e.g. if you were computing a CI, you might want to investigate the impact on coverage -- e.g. how much would a 95% interval only giving 92% coverage matter? Sometimes the deviation may be a minor issue, at other times you might care a lot. If you're making a forecast, you might wonder what might the effect on the MSE of a prediction be? .... or many other things beside those)
This is not a matter of proof, though, just investigation. It might involve bootstrapping the sample, or sampling a "fuzzed" version of your sample, or looking at simulation from models that generalize your simple model in ways that more nearly encompass your data, or a number of other possibilities.
Find the most fitting distribution parameter (lambda) with 95% probability.
We can optimize parameter estimates according to any number of criteria (find the 'best' for a long list of potential choices of what you regard as 'better' which criteria you have not stated), but the "with 95% probability" part doesn't seem to make sense; I'm not even sure what you might have been trying to express there, if anything specific; were you looking for an interval estimate as well as a point estimate?
What would be the best scientifically acceptable approach in this situation
I'm unclear what counts as scientifically acceptable. What are the criteria for this? Who is judging them?
* the one you have a sample from and the one you're using as a model.