Transforming an NFA into an NFA of similar size but without $\epsilon$-transitions
The obvious answer is: the powerset construction gets rid of $\varepsilon$-transitions, so you can use it. It blows up the automaton exponentially in the worst case, though, so it is not directly applicable. However, you can use the part that deals with $\varepsilon$-transitions and keep nondeterminism.


   That is, if a state $q$ has an $\varepsilon$-transition to $q'$, add all outgoing transitions of $q'$ to $q$ and remove the $\varepsilon$-transition.
 You have to iterate this process for every state because there may be chains of $\varepsilon$-transitions. In the worst case, you reach all transitions (for every state), causing the required runtime bound (to be sharp).


Note that formally, this does not change the number of states. It might lead to isolated states, though, that can safely be dropped.