The title says it all really - are there any good alternatives to Linoleum and Wood for relief printing? Note that I'm already aware of specially made lino alternatives such as softcut etc; I'm more interested in materials not made/developed for the purpose that can be used.
Anything you can cut into can be used to make a matrix for a relief print. Different materials have their peculiarities in terms of work process and result (compare linocutting to woodcutting), so it depends on what you are trying to achieve.
Here are some materials I've tried in the order I'd recommend them:
PLYWOOD Pretty much like solid wood, comes in large sizes, cheaper than solid wood. Note: There are different types of plywood, and they behave differently when cut. Choosing some soft wood to begin with may be a good idea.
HARDBOARD Advantages: easy to cut, cheap, comes in large sizes Disadvantages: produces a dusty mess, needs sealing, it is somewhat difficult to get fine detail
MDF Same as hardboard, but a bit heavier
OSB Advantages: cheap, comes in large sizes Disadvantages: difficult to cut, easy to slip blade and cut yourself, dulls blades, does not work well with fine detail or on a small scale, heavy, easy to get splinters Note: Unless you have nothing else to cut, it is really not worth it.
It's difficult to recommend a material without knowing what kind of result you want, or why linoleum and wood are not desirable. @user18894 presented some good wood-like materials; I used MDF for years, and was very happy with how well small detail held up, and how easy it was to carve. I never sealed it.
As a comment mentioned, you can use many food items by carving into them and creating a stamp/matrix - potatoes, carrots, cabbages. They each will have a particular texture, and tend to degrade quickly.
You could also use clay, either moist or in the bisque stage. The two states will obviously provide different challenges to printing and durability.
Plexiglass is an option, but is typically used for intaglio printing.
You can also build a matrix out of material. For example, glue/layer things like masking tape, leaves, lace, or paper on top of cardboard and roll ink onto that surface. Depending on your materials, this will also degrade fairly quickly.