As the title asks, could [j] and [ʎ] coexist in the same language as distinct phonemes? I imagine one would merge with the other or some other mechanism forms to make each more distinct. If the speakers had hearing exceeding that of humans, would this feature be more viable? Just a thought of mine.
Such a distinction is pretty common across Romance languages, and a distinction between /ʎ/ & /j/ is preserved in Italian, Occitan, and most of the languages of Iberia (this latter phoneme is also often transcribed /ʝ/ in some languages). Spanish itself is unusual amongst the languages of Iberia in having mostly lost this distinction (with both undergoing yeísmo, merging /ʎ/ into /ʝ/), although lleísmo (with the distinction) is still the official standard in Spain itself, and preserved in some dialects (especially when spoken by people who speak other languages of Iberia).
Going through PHOIBLE, the vast majority of languages with a /ʎ/ also have a distinct /j/. There were 94 distinct languages with /ʎ/ in at least one listed inventory, of which only something like 7 languages (Ayacucho Quechua, Jungle Inga, Kabuverdianu, Liko, Pampanga, Paraguayan Guaraní, Serbian) didn't have a /j/ listed in at least one inventory. That's >90% of languages with a /ʎ/ also have a distinct /j/. From that, if it's natural to have a /ʎ/ phoneme, it must be natural to have distinct /ʎ/ and /j/ phonemes.