Plaster of Paris? It is very cheap, easy to cast and easy to work. You will need to spray with some sort of varnish to strengthen the pieces, even for a prototype. Might work for larger solid pieces.
Milliput or another 2 part epoxy clay might be worth a try.
Even regular clay (Fimo?) might work for some things, it does shrink a bit though.
I guessing but you are probably going to need quite strong small parts for the "active" bits. You might want to make these from stock shaped plastic. Model shops sell all sorts of different shaped extruded rods and you can also get sheet material. They also sell small metal stock, this might be good. You can get all sorts of rods, springs, cams, gears, bearings etc. Soldering is cheap and easy and might be strong enough for what you want, brazing can be done with a gas cooker!
Try and use existing puzzle pieces where possible, even if they need a lot of modification. You can make some interesting shapes by cutting, grinding and gluing production bits.
Don't give up on resins. Polyester is very cheap (~£5/kg). A kilo makes a lot of pieces! You can bulk it out with microdol (a mineral powder), this stuff only costs £0.65/kg and you can add up to 4:1 by weight before the resin stops pouring well, if anything it makes pieces stronger.
If you are only making a few of a piece you don't need expensive silicone for moulds. Try things like wax, plasticine or vinamold (http://www.vinamold.com/
). Vinamold is a cheap (<£5/kg) meltable self lubricating rubber, it is very fluid at 180 deg C and works well, it stinks though. You heat it in a jug in the oven then pour it over your piece and let it cool. You can chop up the old moulds and reuse the stuff. Obviously you can't take a mould of a piece made from thermoplastic, because the heat will distort/melt it. So don't pour it on any production puzzle parts, your own polyester, polyurethane, epoxy, clay, milliput, wood (sealed with varnish), metal... parts will be fine.
You will probably need to get a dremil type tool, if you don't have one. And a big bag of lego bricks if you want to do moulds ;)
I would love to see a 7x7x7 but I think it will be very very hard to do. Why not try the system on a large 3x3x1, a puzzle which would also need a similar type mechanism to hold on the corners. This would have the advantage of working at a better scale and you would create a very unique puzzle! I should still show that the system would work for a 7x7x7. You might even be able to get away with chopping up one Rubiks jumbo 2x2x2 for the cubies and use a cut down spider from a cheap 3x3x3.