Lorsqu'on fait suivre envie par un verbe, par exemple, dans « ce que j'ai envie de dire », le pronom « que » est l'unique possibilité car il est complément d'objet direct de dire. Pour désigner directement l'objet d'une envie, avoir envie étant suivi de la préposition de, on utilise normalement dont pour former une relative : « ce dont j'ai envie ».
Cela explique que tu obtiennes les deux possibilités en faisant des recherches sur Google N-gram. Le fait que les proportions ne soient pas tout à fait les mêmes pour « envie » et « besoin » est probablement dû au fait que l'un est plus souvent suivi d'une proposition infinitive que l'autre.
Petite remarque : « Je fais ce que j'ai envie » ne me choque pas car ça se comprend comme une ellipse : « Je fais ce que j'ai envie de faire ». On l'entend parfois en entier, mais c'est aussi courant de ne pas répéter un verbe lorsqu'il est connu. Un exemple similaire serait « Chante ce que tu veux ! » qui sera la plupart du temps compris comme « Chante ce que tu veux chanter ». Seulement dans de très rares cas ce pourrait ne pas être une ellipse et vouloir dire « Fais ta requête en chantant ! ».