Will the Boeing 737 MAX 8's software update require recertification of the aircraft? Will the upcoming software update for the 737 MAX require the plane to go through a new certification like a new plane?
Nope

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.