How to do the following query without using INNER JOIN?

Answering the question: No. You have two different keys and you need a JOIN for each key to fetch the description from the second table.

Any solution other than this will either change the result of your query, or else resolve it out of the database (by the application, generating a collection of countries and assigning the description).

Yes, just use different aliases for the table in each JOIN :

SELECT 
    Envios.*,
    PaisEnvio.nome_pais AS nome_pais_envio,
    PaisRecibo.nome_pais AS nome_pais_recibo
FROM Envios
    INNER JOIN Paises AS PaisEnvio
    ON PaisEnvio.id = Envio.id_pais_envio
    INNER JOIN Paises AS PaisRecibo
    ON PaisRecibo.id = Envio.id_pais_recibo 

Use the following query:

SELECT PAIS_ENVIO.NOME_PAIS, PAIS_RECIBO.NOME_PAIS
FROM A
INNER JOIN B PAIS_ENVIO on A.ID_PAIS_ENVIO = B.ID
INNER JOIN B PAIS_RECIBO on A.ID_PAIS_RECIBO = B.ID

set @entrada = 23;
set @saida = 47;

SELECT 
    e.id_pais as entrada, s.id_pais as saida
FROM
    tbl_pais s,
    tbl_pais e
WHERE (s.id_pais = @saida AND e.id_pais = @entrada);

I would not know another way to do it without some kind of join ... Thanks! : D

With Sub Query or Sub Select:

SELECT 
   TabelaA.ID, 
   TabelaA.ID_PAIS_ENVIO, 
   (SELECT TabelaB.NOME_PAIS FROM TabelaB WHERE TabelaB.ID=TabelaA.ID_PAIS_ENVIO) AS NOME_PAIS_ENVIO,
   TabelaA.ID_PAIS_RECIBO,
   (SELECT TabelaB.NOME_PAIS FROM TabelaB WHERE TabelaB.ID=TabelaA.ID_PAIS_RECIBO) AS NOME_PAIS_RECIBO 
FROM TabelaA

Reference:

• Working with Subquery's

You can do without join by linking the tables in the WHERE.

   SELECT a.id
     , a.id_pais_envio
     , b_e.nome_pais as nome_pais_envio
     , a.id_pais_recibo
     , b_r.nome_pais as nome_pais_recibo

  FROM tabelaA as a
     , tabelaB as b_e
     , tabelaB as b_r

 WHERE a.id_pais_envio = b_e.id
   AND a.id_pais_recibo = b_r.id