I am wondering if there are polynomial time computable invariants of topological spaces (say, finite simplicial complexes, or finite CW complexes with computable attaching maps to be a bit more general) which are somehow fundamentally different from homology? Certainly cohomology admits a ring structure, but this is really just more structure on a homology group. Is there something "in between" say homotopy groups and homology based structures?
There are several questions you ask, and I think I can say something about the last question.
It is worth thinking about the origins of homology, see for example essays in IM James (editor) "History of Topology". The early writers on what we now call algebraic topology wanted to take "cycles modulo boundaries" but were not too clear about the meanings of those words. It was Poincar\'e who brought in the idea of "formal sums" of oriented simplices, and so the famous equation $\partial \partial=0$, defined on what we now call a free abelian group. The work of E Noether led to the abelian group theoretic formulation of homology we know today.
The topologists of the early 20th century, such as Dehn, were well aware, particularly by the 1920s, that for a connected space $X$ the first homology $H_1 X$ was $\pi_1(X,x)$ made abelian, and that the nonabelian nature of the fundamental group was important in applications in geometry and analysis. So they looked for higher dimensional versions of the fundamental group.
In 1932, E. Cech submitted a paper on higher homotopy groups to the ICM at Zurich, but Alexandroff and Hopf persuaded Cech to withdraw his paper on the grounds of their abelian nature (it is not clear if this was known by Cech or was proved by Alexandroff and Hopf). Later, worries about the abelian nature of the homotopy groups would be seen as a quirk of history.
However work was done on the generally nonabelian second relative homotopy groups $\pi_2(X,A,a)$ by JHC Whitehead, who introduced in 1946 the notion of crossed module, and in 1949 the notion of free crossed module. This allows one to say that for the standard diagram of a Klein bottle, we can write $\delta \sigma = a+b-a +b$, with values in the free group on generators $a,b$. He pursued these ideas in his 1949 paper "Combinatorial Homotopy II".
Now the reason for the abelian nature of the higher homotopy groups can be put as that group objects in the category of groups are just abelian groups.
There are arguments for phrasing the theory of the fundamental group in terms of groupoids. It then turns out that group objects in the category of groupoids, or groupoid objects in the category of groups, are equivalent to crossed modules, see this 1976 paper.
This was part of a search for Higher van Kampen Theorems started about 1965, whose results are described in this 2011 book Nonabelian algebraic topology and this 1992 expository article, which deals also with some algebraic models, cat$^n$-groups, of homotopy $(n+1)$-types, and calculations involving these. Note that the book does not require the development of singular homology, even for a statement and proof of a Relative Hurewicz Theorem!
What may be seen as a catch is that the strict higher homotopy groupoids used are defined for filtered spaces and $n$-cubes of spaces, not directly for spaces. (The original question does not say of what we should have invariants!) My own view, influenced by spending 9 years on trying and failing to define a homotopy double groupoid of a space, is that the emphasis on theories for spaces without additional structure is likely to be a mistake: this is kind of confirmed by remarks of Grothendieck in Section 5 of his 1984 "Esquisse d'un Programme". (See my comment below for a link to this work.)
Just to develop the last point, the usual method in singular homology is to define singular homology of a space and then after a lot of palaver to get the cellular chain complex of a CW-complex, based on its filtration by skeleta. Instead, one can define homotopically invariants of any filtered space, and then one needs quite a lot of work to show how to calculate them for a CW-filtration, but in the process gets more information since we deal with nonabelian structures in dimension 2 and keep the operations of the fundamental groupoid.
As regards computation, this is always a question in dealing with nonabelian methods; but the above cited book has many calculations involving crossed modules, and so second relative homotopy groups, while one spinoff from the work on cat$^2$-groups, a nonabelian tensor product of groups, has had lots of work mainly by group theorists, see this bibliography, with 130 items.
What does seem to be lacking in this work is the vision of the workers of the early 20th century, namely the applications of these particular nonabelian methods in geometry and analysis!
I have attempted to indicate some work "between homotopy and homology"; it seems to me to deserve this appellation, because it involves homotopically defined functors, and honest (partial) compositions of mappings defined by using gluings of cubes, not the "trick" of using free abelian groups.
I am not sure if this answers your question.