But if you randomize, then you have the risk of placing the coin at a location where it can be easily found, like on a table or on the floor.

That's not really a problem--you could just randomize over the set of not-obviously-visible locations. You could even rearrange the furniture and objects in your house such that the rearranged version has more hiding spots than the current arrangement of furniture.