Can gain and phase margins be obtained from step responses?
"Can step responses be used for this?"

The answer is yes as long as the PHASE margin is concerned - provided you have a linear second-order system.

Relevant books and articles contain a formula which relates the phase margin to the pole Q of the system. Because - on the other hand - the pole Q is related to the step respose overshoot, there is a curve which connects overshoot (in %) and the phase margin. For example, for a phase margin of 30deg the corresponding overshoot is app. 38%.
(see, for example, S. Franco: "Design with operational amplifiers and analog integrated circuits", McGraw-Hill, 2nd ed., page 354).

As far as I know, a similar relationship does not exist for the gain margin.