The inclusion-exclusion principle doesn't work.
Example of good path is:
$$ 1\to 2\to 1\to 4\to 3\to 2\to 1\to 4\to 3\to 2\to 1\to 3\to 2\to 4\to 3\to 4$$
This one isn't:
$$ 1\to 2\to 1\to 1\to 3\to 2\to 1\to 4\to 3\to 2\to 4\to 3\to 2\to 4\to 3\to 4$$
because the $1$st city gets consecutive visits.
In graph theory the problem would be: How many paths are there in a simple undirected complete graph with $4$ vertices so that each vertex is visited exactly $4$ times.
After n visits to cities, we are in a state (a, b, c, d), where a is how often the last city was visited, and b, c, d is how often we visited the other cities. a+b+c+d will equal n. a, b, c, d are all 4 or less. We may assume that b, c, d are arranged in descending order (for example 2, 3, 2, 0).
In the first move, there are four ways to enter state (1, 0, 0, 0). Then in every move, we can visit a city other than the last one visited which hasn't been visited yet. Combine the numbers how often identical states can be visited.
x cities visited at most y times works easily in y^x * y * x steps; polynomial for any fixed x.