After spending two evenings on this problem, trying all the above solutions, these steps finally did it for me:
On Mac:
Disable "Automatically manage signing" inside xcode.
Unpair device from xcode (inside Device manager)
Navigate to ~/Library/MobileDevice/Provisioning Profiles/ and i deleted the existing profiles
On phone:
Delete the broken app
Open up your phone and navigate to Settings -> Developer and then press "clear trusted devices"
On Mac:
Open xcode and enable the automatic code signing again
Pair device again
Voila.
I hope this might help someone <3