There is actually a solution which I thought of a while ago, but then forgot of until last night, and it was how I was planning on doing it. It's not perfect, but I think will be interesting to see how it plays out.
Each time you step on a tile with a resource/bonus you have a percentage chance of discovering it. This will be say a base 10% chance, with techs, civ-level or unit-level enhancements which increase the odds. (After all, a tile is a big area, and you aren't necessarily going to stumble on it immediately). I think that city-radius tiles would naturally be uncovered by being worked (with the same or higher chance per turn). Therefore you are reasonably unlikely to find something outside your territory unless its on a commonly tredded path. Workers performing actions on a tile would also increase the odds.
Once discovered, it of course stays discovered. So you can discover coal, before you have the techs to use it. There are two branches here, and I haven't decided which way to go:
* Simple - you can't mine it at all, until you have the proper techs
* Advanced - you can mine it BUT only under a trade agreement where the party you are trading with:
- has the required techs
- where their worker unit builds the mine (which will require a special access agreement).
- ALL coal must be traded to them (you cannot stockpile a resource you have no value of).
- If the trade agreement is broken for some reason, then the mine is abandoned (no more mining), but the infrastructure remains there until you have the required techs, or can establish trade for the resource with another civ with the required tech.
Resources have a quantity, which decreases over time. When you first discover a resource you will not know how much there is of it (which requires a specialist or upgraded worker to investigate the tile. Then, before modern times there will be an error margin applied, so you don't know exactly how much of a resource you have). The ones you see on tiles will be surface and shallow-crust level resources.
In later-game, specialist units (or upgraded workers) will be able to do core samples testing for resources in a below-surface level. (Automated method) It is possible for a surface tile to have no resource (e.g. coal) but for a lower level to have it.