Fine-grained sensing of distance between two permanent magnets
Yes, you will be able to use a coil to produce a varying voltage which you can then amplify and input to a microcontroller. While it would be possible to provide a coil that produced signals at a level suitable for direct input to a uC ADC, in most cases you will end up with very small signals which need to be amplified.

Use of a linear hall cell is liable to be easier overall.

The A1301 is a good choice. Not in stock at Digikey.

Digikey do have this Honeywell SS39ET Hall sensor that looks good.
 $1.44/1 in stock