In the first school I started in, they had a mat made from plywood and old carpet and carpet padding. Just build a frame with 2x4's laid flat so it's 2" high. Then make your flat surface on top with plywood. This will have some give as long as you don't put the braces too close together. Then, lay down carpet padding and carpet or a couple layers of padding, or 2 layers of carpet (depends on your available resouces) . Ours was just the plywood frame with 2 layers of carpet and it was easier to fall on then the first one we had with polyfoam padding. Anyway, lay your vinyl down on top of the carpet, take time to stretch it tight, and fasten it to the outer frame. (the vinyl can be expensive to get depending on the size of your mat)
Now, all of this may be silly to even suggest given the fact that you could probably by old wrestling mats from craigslist or the like (as already mentioned) and there are lots of modular systmes you could buy to build with interlocking 4x4' or 3x3' squares that fit together to make your space. I could be wrong about the size but I'm estimating based on what I've seen.
If you want to go old school, find a patch of soft, well-maintained grass or a clear stretch of sand and have at it.