The first sentence implies a missing facility to get rid of the rubbish. Whereas in English, the interrogative particle "what" relating to the rubbish itself is combined with "into" to indicate a movement in a certain direction and to a place, in German you start with a local relation using the interrogative particle "wo", but only in a general sense, because after that, you have to specify whether you're speaking of a movement or something that has already been moved to a place. This is done with a verb:
Ich wusste nicht, wo ich den Müll hineintun / hineingeben sollte (the rubbish ready
to be moved, but where to?): "hinein" (into) combined with "tun" or "geben"
"...wohin ich den Müll tun/geben sollte" is not sufficient, because it would imply that the dust should be placed somewhere, but not "into" somewhere.
Ich wusste nicht, wo der Müll sich befand (rubbish previously moved
somewhere, but where?)
If you don't use a verb, you have to specify the movement by the question word:
Ich wusste nicht, wohin mit dem Müll.
But this is not the proper equivalent for "I didn't know what to do with the rubbish", because it restricts the statement to putting the rubbish somewhere, while "I didn't know what to do with it" can have several meanings: E.g., you have produced some rubbish and want to put it somewhere, or you see the full bin bag in the kitchen and want to get rid of it but don't know how, and so on. Therefore, you would say in German:
Ich wusste nicht, was ich mit dem Müll tun sollte.