"He's so shy. I could never tell he has a girlfriend."
"He's so shy. I could never say he has a girlfriend."

Is there a significant difference in meaning between those sentences? Do they sound natural?

"Considering how shy he is, you could never tell he has a girlfriend."
"Anyone who sees how shy he is, could never tell he has a girlfriend."

Does the sentences above sound natural?

Vedi una traduzione

The two sentences have different meanings.

"I could never tell he has a girlfriend" means you wouldn't know he has a girlfriend (because he's shy).
"I could never say he has a girlfriend" means you wouldn't speak about the fact he has a girlfriend.

"Tell" and "say" aren't interchangeable. In Portuguese, think of the difference between "contar" (uma história) and "dizer" (uma coisa). The same distinction exists between tell and say.

In this case, though, "tell" means something else: notice, recognize, distinguish between: I can tell you work out (because you have defined muscles). I can't tell these two things apart (because they look the same to me). "Say" can't mean those things, so it doesn't work in your sentences.

"Considering how shy he is, you could never tell he has a girlfriend."

This sentence is fine. You could also phrase it like this, if you want to keep the word "tell":

"Considering how shy he is, you'd never be able to tell he has a girlfriend."

This sounds a little bit more natural in an informal context.

"Anyone who sees how shy he is, could never tell he has a girlfriend."

The comma is awkward because what comes after it has no subject. It should be:

"Anyone who sees how shy he is could never tell he has a girlfriend."

And again, you can phrase it like this to make it more natural/informal:

"Anyone who sees how shy he is would never be able to tell he has a girlfriend."

Let me know if you prefer an explanation in Portuguese.