The blocks contain the complete transactions. When you validate a block, you validate every transaction in it the same way the miner who mined that block presumably did.
To spend a previous transaction's output, you must provide a valid signature.
Every signature is accompanied by a public key in the transaction. If you have a signature to verify, you also have a public key.
On the other hand, it's just for the outputs of a transaction that you have only an address. However, there is nothing to verify then since there's no signature. There is no need to validate an address. What would an invalid address be?
The only thing they need to validate are signatures and, as I said, signatures are always accompanied by a public key. When a transaction contains a signature, that signature is accompanied by a public key. Where a transaction does not contain a signature (such as for its output addresses) there is no signature to validate and hence no need for a public key.
The important thing is that the miner validates the transaction and then includes the transaction in the block, so everyone else has everything the miner had.