Re: slightly soft floor remedies
The best tool ever for cutting new soles is a router with a flush trim bit. A router table works even better, but if you don't like wood working can be an expensive investment. Do the rough cuts to general dimensions with a jig saw, and a flush trim bit with the old piece (template) clamped to the new board.
The flush trim bit will follow the edge of the template, and give you a piece that is exactly the same.