The excess growth of digital information on the Internet and the excessive use by many users have created an issue of information over-load, where the data remains unfiltered and uncategorized. Many large corporations, like Deezer, JioSaavn, Spotify, and Wynk music streaming apps, have included recommendation algorithms to assess possible consumer preferences and propose suitable products to the user. However, it can be challenging to recommend an item to a new user with minimal or no interaction with the system. This problem is popularly known as the new user cold start problem, which refers to the issue of recommending music to users with little or no listening history. Deep learning-based approaches have recently shown great potential in addressing this challenge. This paper aims to extensively analyze the latest deep learning techniques to tackle the challenge of the new user cold start issue in the music recommendation field. Additionally, the paper explores the potential of using supplementary data such as user profiles and lyrics to enhance the performance of deep learning-based methods. Finally, we critically analyze the current state-of-the-art and identify open research directions for future work. This paper provides a valuable resource for researchers and practitioners in the music recommendation domain who seek to use deep learning-based approaches to tackle the new user cold start problem.