As autonomous driving technology progresses forward, Frequency Modulated Continues Wave (FMCW) radar is projected to be used more widely for automotive purposes. Due to the expected rapid growth of road vehicles equipped with radars, more attention is paid to finding ways of reducing mutual interference among automotive radars. In this letter, a novel scheme is proposed to solve the issue of velocity estimation for FMCW radar with random pulse position modulation, which is a promising technique to drastically mitigate mutual interference. The proposed scheme uses a 2-D Convolutional Neural Network (CNN) working on covariance matrices of signals extracted from regions of interests as well as the information of chirp positions. Analysis of its performance, in particular comparison with that of Orthogonal Matching Pursuit (OMP), with simulation and experiment data demonstrates the potential of the approach.