"He was learning to do it with a new tool."
Translation:Učil se to dělat novým nástrojem.
It is my understanding that, in a sentence like this, the use of the preposition "S" would be incorrect. When the instrumental case is used without the preposition, the sense of "with" is "by means of." When the preposition is used, the sense of "with" is "together with."
----- UPDATE -----
You may be able to find an online copy of Karel Tahal's Grammar of Czech as a Foreign Language. A good explanation of the different uses of the instrumental case, including how it's used in this sentence, is contained in Chapter 31 (p. 113). Happy learning!