Your needs look reasonable. Non-toxic is good to know but won't rule many elastomers out.
My suggestion is that you
query an elastomer company. Dozens of plain elastomers and their foams (or even a tyre) look still possible based on you description, and the hardness is
very widely adjusted for one single chemical composition, by the degree of cross-linking among others. That's a specialist job for a specialist company. And don't get afraid by qualitative answers: numbers and equations have a limited usefulness with rubbers.
Do you have some more constraints?
- Shall it give the deformation energy back (only natural rubber excels at it) or absorb it (PU does, and most foams too)?
- Do you accept a long-lasting deformation after a prolonged compression?
- Heat, cold? Both are difficult for rubbers.
- Prolonged exposition to sunlight? To UV? To ozone? Ionizing rays?
- Warm water for long? Chemicals? Operation in vacuum?
- What force shall compress your brick from 12in to 5in?
Try not to exaggerate these constraints, because some rubbers are really expensive and your brick is big.