How does publishing in the deep learning world work, with respect to journals and arXiv?
Let me answer your questions one by one.

Submit it to a conference

Let's start with the optimistic case. Say your paper gets accepted! You can upload your preprint on arXiv with the "arXiv.org perpetual, non-exclusive license to distribute this article (Minimal rights required by arXiv.org)". It is a non-Creative Common License that does not provide any exclusive rights to arXiv as per. This is the default permission of arXiv (which does not interfere with the license of the conferences). You can easily find papers from ICML, NeurIPS, and AAAI on their websites as well as arXiv. For, e.g., NeurIPS 2017 began on 4th Dec 2017 and this paper has the latest submission on 6th Dec 2017.

If you say your work was rejected or you are about to submit it, you need to check for the restrictions on uploading the manuscript online before submitting it to the conference. Some conference allows papers to be submitted only if they are not uploaded to sites like arXiv within say 30 days prior to the paper submission deadline.

AAAI does not have restrictions on arXiv as per their policy. ACM also allows non-profit organizations like arXiv as per their policy.
Among all the info on the major publications I could find, I found a common phrase that the paper should not be uploaded to a for-profit digital library. ArXiv is certainly not among them. The reason why editors do not oppose arXiv papers could be that there are a lot of papers that are uploaded to arXiv in order to claim to be first, so banning them would be a big loss for the editors.

Say you comply with the restrictions of the conference and have uploaded your preprint then it brings the risk that reviewers can know who the authors are. They might be biased once they know who the authors are. This works in the favor of renowned/superstars scientists of the field. The reviewer might be a Ph.D. who admires this superstar and hence would try to get it accepted. Or the author might be a known colleague of the author and would hence be biased into accepting it. On the other hand, if the reviewer has some personal bias towards the author then that may be reflected in their scores. 

Upload it on arXiv directly

Only uploading to arXiv is of not much academic value because it is not peer-reviewed as you pointed out. Anyone can write an absurd paper with false results and get it published on arXiv. That is why peer-reviewed papers are important.

One reason to upload to arXiv first is to make your work safe from other people coming up with similar approaches. It is not rare at all for people coming up with similar ideas within a duration of 3 months. Deep Learning is a fast-paced domain as it is a hot research field. So getting your paper out first in the name of work in progress saves you from potential rejects from the conference pointing to a similar work done available online before you.

Submit it to a peer-reviewed journal

Same thing as a conference. You can upload your preprint after acceptance of your manuscript with the default license of arXiv. For submitting it before on arXiv needs cross-checking with the rules of the journal. For, e.g., IEEE allows the work to be submitted to arXiv as per.

How do big stars publish?

Coming to your question of how big stars publish. They either publish directly in a conference and then upload to arXiv or they first upload on arXiv, get publicity and citations and then submit to a top conference. Having the preprint available online can also bias the reviewer into accepting their research (as mentioned before). This way they reduce their chance of rejection.

Fun fact

Interestingly, if the preprints become very famous then the reviewer might get confused that your work is a derivative of a popular work which in reality is the preprint of your submitted work! In such cases, you would need to imply this diplomatically. For example, Music Transformer by the Google Brain team (which consisted of authors of the famous Transformer paper "Attention is all you need") was available on arXiv in 2018 and was already being cited by others. When it was submitted to ICLR 2019, a reviewer mistakenly took it as a derivative work of the 2018 arXiv paper and suggested a rejection of the paper. However, after further inspection, he/she realized the confusion which blew their mind! Immediately the paper was given a suitable high score. Source: https://openreview.net/forum?id=rJe4ShAcF7

Where to publish?

Unlike in core electronics and other branches where a journal is much more important than conference papers, in machine learning, conference papers are at par or better than any journal out there. Mostly the quality depends on the Impact Factor of the journal or conference. For example, NeurIPS is a top venue to publish and it's a conference and not a journal.

One reason for conferences to be so important is that they are more popular among researchers. Conferences are fast with their review as compared to the lengthy journal review. This allows researchers to meet and discuss the progress of the field with like-minded people much faster. This is crucial for a rapidly evolving field like artificial intelligence. This makes conference popular which attracts the best researchers to publish their cutting edge which in turn makes the conference more lucrative for other researchers to publish in the same venue as the big stars. 

Conferences also allow people from the industry to meet the researchers and hire them. The quick meeting opportunity provided by the conference is beneficial for both the academic researchers as well as the industry for attracting talent.