I implemented the idea by using some leftover wood balcony decking, magnets and a drill. The point is to drill a hole on the wall-side to a depth that leaves 1-3 millimetres of unbroken wood on the face-side of the key holder. I didn't get it perfect, the drill bit I used had a fairly long center point so I had to poke a tiny hole through.
1. Choose your key holder, anything that you can drill a hole in.
2. Drill holes on the back side, but stop before you puncture through. Thinner is better for magnetic field strength, but increases risk of getting an ugly scar. Probably best to use a bit that is flat on the front and use a smaller diameter bit to center the larger one. I used a 10 mm drill bit. Tip from image71: Use a Forstner bit for that flat hole finish.
3. Insert magnets of your choosing. I had Ø10x2 mm neodymium discs purchased from a home depot kind of store. They were rated to hold 900 g each. Interestingly, while testing I found that anything over 3 mm face thickness would be too weak to hold my keys. In hindsight, this K&J magnetic field strength calculator says that a Ø10 disc that can hold 998 g at 0 mm distance, will only be able to hold 95 grams at 3 mm distance. My keys weigh about 80 g. Give and take some uncertainty there and I think you can use that calculator to plan your design very well.
4. Add a drop of glue, to keep your magnets in place.
Tip: Remember that you have a magnetic field on the wall side as well! If you already have a screw or bolt in the wall, try hanging the key holder on the bolt. If the screw head can touch the magnet through the hole, you may have yourself a pretty strong grip.
That's it! Needless to say, there are some improvements to be done on the method so comments are very welcome! :)