I wasn't able to build for 16.4 after upgrading iOS on my phone, too. Since Xcode did not support 16.4, yet.
Today a new version of Xcode was released. I guess it will fix this issue.
However, I was able to solve this by doing the following:
Download the Xcode release candidate 3 (RC3) from the Apple Developer web site and extract it. You then have to right click on the extracted app and select »show package contents«. You then need to copy the files from Contents/Developer/Platforms/iPhoneOS.platform/DeviceSupport/16.4
to Contents/Developer/Platforms/iPhoneOS.platform/DeviceSupport
within your currently installed version of Xcode.

As mentioned above, the new release will probably fix this, but this workaround might be useful for future iOS updates.
UPDATE:
The latest version of Xcode (14.3) introduced the same issue for me. I was able to fixe the issue by modifying my ios/Podfile
to set the level for deployment targets to 11.0.
post_install do |installer|
installer.pods_project.targets.each do |target|
flutter_additional_ios_build_settings(target)
end
installer.generated_projects.each do |project|
project.targets.each do |target|
target.build_configurations.each do |config|
config.build_settings['IPHONEOS_DEPLOYMENT_TARGET'] = '11.0'
end
end
end
end