Will the upcoming software update for the 737 MAX require the plane to go through a new certification like a new plane?
Updates like this are generally deployed under an Airworthiness Directive ("AD") and in this case will likely be required although not all AD's technically are. AD's are issued against Type Certificates or serial number ranges, or possibly even individual parts. They are publicly published and when it becomes available the FAA will post it here.
Certifying a new airplane, or even a new version of the type as with the MAX, is a huge deal. It does not make sense to go through the whole thing again just for a fairly minor change.
However, once a plane is certified, the entire design and configuration is fixed. Any changes have to be approved to allow the plane to be considered airworthy as an example of the certified type. The manufacturer will have to show that any change will either not change the basis of the original certification, or if it will, to justify how it will maintain at least an equivalent level of safety to the original configuration, and meets the regulations.
Boeing will certainly have to test a software change to MCAS, just as with any change the modifies aircraft behavior. The FAA will have to sign off on the change once they review the certification and any test data and find it meets regulations. For some tests the FAA requires that an FAA inspector be on board to witness the test, and given the profile of the situation and the scrutiny being applied, that may be the case here.
Of course, if an aircraft is operating under a different regulator, such as EASA, that regulator will also need to agree that the modifications meet regulations. For small changes they may defer to the main regulatory body, but again with the scrutiny in this case, other regulators will probably be sure to review the changes very carefully before extending their approval.
In cases like this where the regulator believes safety is an issue with the existing configuration, they can issue an Airworthiness Directive that mandates a certain inspection or change. The AD will define when this must happen, and if not accomplished by the deadline, the plane is no longer considered airworthy. The deadline could be a hard date, or within a number of flight hours/cycles.