Short answer
The VAE is not the Auto-Encoding Variational Bayes (AEVB) algorithm or an instance of it.
The VAE is a machine learning model. More specifically, it's a probabilistic auto-encoder, where the probabilistic encoder (aka recognition model) and decoder (aka generative model) are represented as neural networks. (Here, "probabilistic" means that they produce/represent a probability distribution).
The AEVB algorithm is a learning/inference algorithm that can be used to find the parameters of the VAE, i.e. to perform approximate variational inference in the following directed graphical model (figure 1 of the VAE paper). (Note that "inference" in Bayesian statistics has a specific meaning, i.e. the computation of the posterior using Bayes rule)
Long answer
The AEVB algorithm
The Auto-Encoding Variational Bayes (AEVB) is the algorithm used to find the parameters $\boldsymbol{\theta}$ and $\boldsymbol{\phi}$, as you can conclude by reading its pseudocode given in the paper.
The AEVB algorithm stochastically estimates the gradient of the objective function, i.e. the Evidence Lower BOund (ELBO) (equation 3). They propose 2 estimators (equations 6 and 7), of the ELBO (not its gradient, which is computed automatically by back-propagation; note that stochastic estimation of the gradient of the objective function is very common in deep learning: see this). Moreover, the AEVB algorithm also uses the re-parametrization trick (i.e. it samples from $p(\boldsymbol{\epsilon})$ to avoid high variance).
The VAE model
The VAE is the model that you create when you use neural networks to represent the encoder (aka recognition model) and decoder (aka generative model), which are parametrized by $\boldsymbol{\phi}$ and $\boldsymbol{\theta}$, respectively. So, the VAE is not the AEVB algorithm. You use the latter to find the parameters of the VAE.
The authors write in the same paragraph that you are quoting
When a neural network is used for the recognition model, we arrive at the variational auto-encoder.
In the appendix, they also write
In variational auto-encoders, neural networks are used as probabilistic encoders and decoders. There are many possible choices of encoders and decoders, depending on the type of data and model. In our example we used relatively simple neural networks, namely multi-layered perceptrons (MLPs). For the encoder we used a MLP with Gaussian output, while for the decoder we used MLPs with either Gaussian or Bernoulli outputs, depending on the type of data.
Variational and generative parameters
Ok, but what are these parameters $\boldsymbol{\phi}$ and $\boldsymbol{\theta}$?
$\boldsymbol{\phi}$ are the parameters of the variational distribution $q_{\boldsymbol{\phi}}(\mathbf{z} \mid \mathbf{x})$, which is an approximation of the (usually intractable) posterior $p_{\boldsymbol{\theta}}(\mathbf{z} \mid \mathbf{x}) = p_{\boldsymbol{\theta}}(\mathbf{z}) p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})/p_{\boldsymbol{\theta}}(\mathbf{x})$; so, in the case of the VAE, these are the weights of the encoder
$\boldsymbol{\theta}$ are the parameters of the generative model $p_{\boldsymbol{\theta}}(\mathbf{x} \mid \mathbf{z})$; so, in the case of the VAE, these are the weights (and biases) of the decoder neural network
Recap
So, to recap, the AEVB is the training/learning/inference algorithm to find $\boldsymbol{\phi}$ and $\boldsymbol{\theta}$. The AVB stochastically estimates the ELBO (and, consequently, its gradient) and uses the re-parametrization trick. If you use a neural network to represent the encoder and the decoder, you get the VAE, which is not the same thing as the AEVB, the algorithm to find the parameters of the neural networks (i.e. the encoder and decoder).
