We study non-equilibrium phases for interacting two-dimensional self-propelled particles with isotropic pair-wise interactions using a persistent kinetic Monte Carlo (MC) approach. We establish the quantitative phase diagram, including the motility-induced phase separation (MIPS) that is a commonly observed collective phenomena in active matter. In addition, we demonstrate for several different potential forms the presence of two-step melting, with an intermediate hexatic phase, in regions far from equilibrium. Increased activity can melt a two-dimensional solid and the melting lines remain disjoint from MIPS. We establish this phase diagram for a range of the inter-particle potential stiffnesses, and identify the MIPS phase even in the hard-disk limit. We establish that the full description of the phase behavior requires three independent control parameters.