approximation algorithm with polynomial complexity
As you say, we believe there is no polynomial-time algorithm for solving an NP-hard problem. So if we wanted to have a polynomial-time algorithm, it seems like we need to give up the hope of always finding an optimal solution. So you are right: typically, we strive to find approximation algorithms that run in time polynomial in the input size. But sure, there is nothing that prevents you from considering approximation algorithms that run in exponential-time (or for example in FPT-time for some parameter).

Sometimes these approximation algorithms are very simple to state. This is perhaps often the case for greedy algorithms, like the one you mention for vertex cover. To see that it runs in time polynomial in the size of the input graph, you need to perform a runtime analysis in the usual way.