Number 1 would work, but a lot depends on your world. If it is huge, and the islands are far apart, you will spend a lot of time with "misses". Also, can one island be over another? If so, you might end up with just spawns on the upper islands, and nothing on the lower ones.
Number 2 is the right idea. Assuming your islands aren't totally featureless blank shapes, I'm guessing you will be putting other items on the islands beyond spawns, which leads to my suggestion below...
Assuming your world generator has some way to create and place entities on the islands (sprites, NPCs, paths, trigger points, items, what have you), you can just generate a "spawn point" entity as well. It is just an invisible placeholder with a coordinate on your world.
When you want to place (spawn) an enemy or the player, pick one, and put them there. If you want, you can do things like invalidate a spawn point once used so two items won't spawn on top each other. Also, you can filter further to regulate spawns. For example, pick a spawn point, and then search all existing used spawn points. If the new one is closer than some distance to an existing one, reject it. This could be as simple as just keeping your spawners from being too crowded, or even monster distribution - i.e., don't put big strong enemy close together, don't put enemies within X distance of the player, etc.
