Non-brute force algorithm for a Eulerian like path
Regarding the problem of visiting as many vertices/edges as possible without using any edge twice: one can look at this problem as the problem of finding an Eulerian subgraph with a maximum number of vertices/edges.  Or alternatively, as the problem of deleting a minimum number of vertices/edges so as to make a graph Eulerian.
You might be interested in the following paper, which studies the complexity of such problems in detail.  In particular, they show several polynomial-time solvable or fixed-parameter tractable cases.  In particular, the edge deletion problems are solvable in n^3 time if a constant number of edge deletions is sufficient.
https://doi.org/10.1007/s00453-012-9667-x