With pruning, all transactions in the the UTXO set must be stored. There is no point in all nodes storing all this info.
How do you see a node being able to verify a validity of a new block, if it would not have the entire UTXO database?
It would need to have the extended block, rather than just a standard block.
A block at the moment is basically just a header + list of transactions.
<Header>
<transaction count>
tx[0]
tx[1]
...
Instead, the extended block would be something like
<Header>
<transaction count>
tx[0]
<input count>
tx for input 1; merkle path
tx for input 2; merkle path
....
tx[1]
<input count>
tx for input 1; merkle path
tx for input 2; merkle path
...
....
The average transaction is 250 bytes and most transactions have 2 inputs. If there are 4096 transactions in a block, then there are 12 levels of the merkle tree down to the transaction. This gives 32 bytes * 12 = 384 bytes for the merkle path. This means that each input would be around 250 + 384 = 634 bytes.
That gives 634 * 2 + 250 = 1518 bytes for each extended transaction. This is 6 times larger than just including the transaction.
However, once you have all the inputs into the transaction, the node can do the verification without needing a database of all the transactions.
A soft fork could be added setting the maximum extended block size to 6MB (in addition to the normal block representation being limited to 1MB).
When broadcasting transactions, spenders could include the expanded transaction. Some miners might refuse to include transactions received as standard transactions in their memory pools.