Should a new screenshot tool automatically set itself to work on pressing the PrtSc key?

You could perhaps set the keyboard short cut for your app but record what was previously bound to that shortcut. Then on first run (possibly when the user presses prt sc, you could pop up a dialog that asks them something like:

This application has been set as the default screenshot application that will be run whenever you press the 'print screen' key. Do you wish to keep to this behaviour or revert to previous settings?

Enabling them to easily get back to the previous settings if they want.

I think scenario A and C are the way to go.

You could plug into the Alternatives system and add the relevant entry to the System → Preferences → Default Applications screen, like this:

I believe that setting yourself as default on install is fine, however. Displaying a notice on first run asking each user if they want to use the previous default instead would be nice.

(Is it even possible to add a new entry in that dialog?)