They have a concept for a piece of software, we do some analysis and agree on reasonable budget and start agile development.
Good.
However once the client starts to see the product they cant (sic) help but tweak endlessly
Also good.
despite our protests
Why are you protesting? If you're in an agile environment, you are supposed to embrace change, not protest it.
and go massively over budget.
And here we see the problem. When you add something into a project, you must take something (requiring approximately equal time+money) out. Or, alternately, you need to add more time and/or money.
Customers changing their minds is normal, expected, and to a point even required by Agile processes and sensibilities. Whereas more traditional methodologies (such as Waterfall) attempt to reduce the likelihood of change, agile methodologies attempt to reduce the cost.
The problem here seems to be that you aren't reducing the cost - which leads to expensive changes. The traditional reaction to expensive changes is to avoid changes, which seems to be what you are attempting to do.
From an Agile perspective, that is wrong. What you should be doing, instead, is making the change beneficial, rather than costly. Make sure that every change adds value to the project - keeping in mind that the only one who is authorized and empowered to determine value is the customer (or the customer's representative, such as the PO in Scrum).
When the customer comes up with a change like this, you need to make certain all impacts of the change are visible to the customer - they need to give up this other feature, or they need to pay more, or the project deadline needs to be pushed back, or some combination of these. (Worth noting, however, that throwing more money at a problem has its limits in effectiveness.) After this, the customer makes the decision of what to compromise - or, perhaps, they'll decide they don't need their shiny new widget after all.
What is the state of the art in building new software products efficiently as possible?
Massively subjective, if you're talking about methodologies and processes. Not only will opinions differ, but the processes themselves vary in suitability based on the situation. There is no one true 'best practice' for software development.
Should we be prototyping the interface (smoke and mirrors, no backend functionality) until it looks and behaves exactly the way users want it, then build out the functionality?
How far you go with prototyping is a trade-off between giving more 'visible' functionality to the customer sooner versus having more working functionality sooner. Typically, the customer should be the one to determine the value of each, though this varies depending on what process you're doing. In Scrum, for example, if you spend the entire sprint creating a big shiny prototype, and you end up not having a shippable product, that's bad.
The rest of your questions are, as with the 'What is the state of the art?', highly subjective.
