I assume a lack of language barrier means we are unable to, or have extreme difficulty, communicating in any language. I suppose it would be possible. Difficult, unlikely, but possible.
I think ideally if I'd want a genuine relationship - regardless of whether it is romance or not - in such a situation it'd be much easier if we have had shared some experiences somehow. For instance, maybe we went through a difficult situation together that didn't necessarily require language (for instance we are both refugees running away from the same thingr, or had to end up helping each other during a natural disaster, or something) (it is for this same reason that, so I've heard, soldiers who fought in the same war might bond together even if they were are are enemies, as they might share experiences non-soldiers wouldn't understand), or some other situation such as one of us being a foreign exchange student and the other being part of the host family, or we somehow end up trapped in the middle of nowhere. Situations like that that force us to get to know each other.
As someone mentioned above, in such a situation, body language and pidgin language is important. It'd also be important for us to not misterpret anything due to cultural differences, as in this situation miscommunication might arise even more easily due to, well, lack of a common language.
In some ways, though it's not too much different from having a relationship - again, regardless of whether it is romance or not - with someone who is usually quiet. In high school I was friends with this one Korean guy who was extremely quiet and said little, yet we had some sort of respect for each other, and I thought he was a pleasant fellow. Our good rapport was built on deeds and patience, not words.
Anyhow, I vaguely recall one foreign movie (Finnish or Scandinavian or something) that depicted a love triangle between three people who spoke different languages and were stuck with each other in the wilderness.
What's language got to do with it? I've yet to meet anyone who speaks mine.
How eloquent, comic, tragic, dramatic, and thought-provoking, all in one.