How to minimally extend a digraph such that all nodes are on a cycle?
Find all the strongly connected components (SCC) of the original
graph.
Replace each SCC by a single node - the resulting graph $G'$ will be acyclic.
Find all the sources and sinks in $G'$ - let $m$ will be a number of sources, and $n$ - a number of sinks.
Match sinks with sources using algorithm by Eswaran and Tarjan (see here), corrected by Raghavan (see here), then add $max(m,n)$ edges for all the matched (sink, source) pairs. 
Replace each node, representing SCC, by this SCC.


This approach will give you a strongly connected graph provided that the original graph is connected. Your requirement to have all the nodes belonged to some cycle is more weak - for example, a set of SCC's, not connected at all or connected by single edges, satisfies your goal definition.

However, it's unclear if this more weak requirement will allow you to decrease the number of additional edges compared to the number of additional edges, given by the algorithm, described here.