Kosaraju with connections between SSCs (strongly connected components)
Your complexity calculation is incorrect. If for each vertex you go over all of its out edges, in a directed graph you'd only get a $O(|V|+|E|)$ complexity and not $O(|V|*|E|)$. A complexity of $O(|V|*|E|)$ would be the case if for each vertex you performed an operation on all of the edges in the graph, which you have no reason to do.

$O(|V|+|E|)$ complexity is actually the same complexity as calculating the SCCs in the first place, and therefore your general idea can, in-fact, be used (be careful with the details).