A pseudocode environment allowing for mathmode and UTF-8 characters?

Sebastiano's answer works well with UTF-8 based engines. To use with pdfLaTeX you can use \lstset{literate=...}:

\documentclass[a4paper,12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[portuguese]{babel}
\usepackage{amsmath,amssymb}
\usepackage{listings}

\newcommand{\R}{\mathbb R}

% taken from: https://tex.stackexchange.com/a/381647/134574
\lstset{
  keepspaces, % Apparently this works... (https://tex.stackexchange.com/a/46695/134574)
  literate=
  {á}{{\'a}}1
  {à}{{\`a}}1
  {ã}{{\~a}}1
  {é}{{\'e}}1
  {ê}{{\^e}}1
  {í}{{\'i}}1
  {ó}{{\'o}}1
  {õ}{{\~o}}1
  {ú}{{\'u}}1
  {ü}{{\"u}}1
  {ç}{{\c{c}}}1
}

\begin{document}

\begin{lstlisting}[mathescape=true]
Para todo $B \subseteq N$:
  Se as colunas de $A_B$ são linearmente independentes:
    Resolver o sistema $A_B x = b$.
    Se este tiver solução $x$:
      Se $x \geq 0$:
        Definir $v \in \R^n$ de modo a que $v_B = x$ e $v_{N\setminus B} = 0$
        Adicionar $v$ à lista de vértices.
\end{lstlisting}

\end{document}

---

About the spacing issue pointed out in the comments. It looks like there's a bug in listings which, after mathescaped text, the space after literated text disappears. I asked a question about this issue and Ulrich Diez apparently fired out what the problem was.

To fix the problem, add the following definition to your file:

\makeatletter
\def\lst@Literate#1#2#3{%
    \ifx\relax#2\@empty\else
        \lst@CArgX #1\relax\lst@CDef
            {}
            {\let\lst@next\@empty
             \lst@ifxliterate
                \lst@ifmode \let\lst@next\lst@CArgEmpty \fi
             \fi
             \ifx\lst@next\@empty
                 \ifx\lst@OutputBox\@gobble\else
                   \lst@XPrintToken \let\lst@scanmode\lst@scan@m
                   \lst@token{#2}\lst@length#3\relax
                   \lst@XPrintToken
                   % ↓ Missing switch added by Ulrich Diez to fix the spacing issue
                   \lst@whitespacefalse %!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                 \fi
                 \let\lst@next\lst@CArgEmptyGobble
             \fi
             \lst@next}%
            \@empty
        \expandafter\lst@Literate
    \fi}
\makeatother

or, more compactly:

\usepackage{etoolbox}
\makeatletter
\patchcmd\lst@Literate
  {\lst@XPrintToken\fi}
  {\lst@XPrintToken\lst@whitespacefalse\fi}
  {}{}

You should compile the code with XeLaTeX. It works well with this type of coding.

\documentclass[a4paper,12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[portuguese]{babel}
\usepackage{amsmath,amssymb}
\usepackage{listings}
\begin{document}
Português para principiantes with formula
\[A(\lambda)=\cos \lambda + \sin \lambda\]

\begin{lstlisting}[mathescape=true]
Para todo $B \subseteq N$:
  Se as colunas de $A_B$ são linearmente independentes:
    Resolver o sistema $A_B x = b$.
    Se este tiver solução $x$:
      Se $x \geq 0$:
        Definir $v \in \mathbb R^n$ de modo a que $v_B = x$ e $v_{N\setminus B} = 0$
        Adicionar $v$ à lista de vértices.
\end{lstlisting}

\end{document}

Heiko Oberdiek's listingsutf8-package offers a workaround to the problem:

It enhances the syntax of the \lstinputlisting-command so that it can read files that are encoded in utf8 and internally re-encode them in some 8bit-encoding before "feeding" to the internals of the listings package.

In case the latin-1-encoding (ISO8859-1), which is an 8bit-encoding, can encode all characters needed in your pseudocode, you can probably use the filecontents*-environment from the filecontents-package for writing an utf8-encoded temporary file, and then use the \lstinputlisting-command which is enhanced by the listingsutf8-package for reading that utf8-file and internally re-encoding it in latin-1 before feeding it to the internals of the listings-package.

Instead of latin-1, as in the example below, you can use other 8bit-encodings in case they do better suit your needs.

In any case using the listingsutf8-package requires ε-TeX-extensions and the \pdffiledump-primitive from pdfTeX. In other words: No matter if run in .dvi-mode or run in .pdf-mode, you need some pdfLaTeX-engine with ε-TeX-extensions.

\documentclass[a4paper,12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[portuguese]{babel}
\usepackage{amsmath,amssymb}
\usepackage{listings}
\usepackage{listingsutf8}
\usepackage{filecontents}


\begin{document}

\begin{filecontents*}{tempfile.tex}
Para todo $B \subseteq N$:
  Se as colunas de $A_B$ são linearmente independentes:
    Resolver o sistema $A_B x = b$.
    Se este tiver solução $x$:
      Se $x \geq 0$:
        Definir $v \in \mathbb R^n$ de modo a que $v_B = x$ e $v_{N\setminus B} = 0$
        Adicionar $v$ à lista de vértices.
\end{filecontents*}
\lstinputlisting[mathescape=true, inputencoding=utf8/latin1]{tempfile.tex}

\end{document}