Acabei de encontrar a solução para o meu problema,
Agradecimentos especiais ao @Slava por me indicar o caminho, afinal era o iptables.
Então, continuei recebendo uma mensagem "Conexão MySQL recusada" ao tentar me conectar remotamente, então procurei uma maneira de ver os logs de conexão TCP e encontrei o
tcpdump
comando. Ao executar
sudo tcpdump port 3306 -vvv -n
Eu vi a seguinte saída toda vez que tentei me conectar remotamente:
Pesquisei na página de manual do tcpdump e vi que R significa para o sinalizador TCP RST (RESET).
Pesquisei um pouco e encontrei este pergunta e sua resposta aceita me levou novamente ao IPTABLES que @Slava sugeriu desde o primeiro comentário.
Foi quando olhei de perto e vi que meu INPUT ACCEPT tcp:3306 foi definido após a regra REJECT TCP reject-with tcp-reset, portanto, o log estava sendo exibido.

Depois disso, apenas removi a regra para aceitar tcp:3306 e a anexei às regras de rejeição tcp e voila!
iptables -D INPUT -p tcp -m tcp --dport 3306 -j ACCEPT
iptables -I INPUT {line number from the first reject tcp rule} -p tcp -m tcp --dport 3306 -j ACCEPT
O IPTABLES agora se parece com isso e, finalmente, posso me conectar ao MySQL remotamente:

Para listar os iptables com números de linha, digite:
sudo iptables -nL --line-numbers
Considerações finais:
- Isso pode ser melhorado colocando na lista de permissões o endereço IP de origem de onde você está fazendo a conexão remota por questões de segurança.