did you consider gravatar? if it works for your use case, so be it

isn't gravatar just a service to provide like random images? the user should be able to upload a custom one

no, it allows users to associate their email addresses with custom images (global avatar). if the user has not done that, it shows a random kinda-unique image instead.

as I understood now, the user would need to register themself on gravatar. reluctantly want to do that, rather leave the possibility to upload, remove etc. on my side

yeah understandable, it just popped to my mind as a solution that is free to implement and needs no maintenance. not sure if there are api or embed options that would make it more native to the website.
a cheap option might be one of those storage servers that you can find on low end box — be sure you get a reputable provider. but i guess you don't need to address this problem prematurely, use your own server (or a service that has free/cheap tier). once you have enough users that you need to pay much for that, then your app/site should be generating enough revenue to cover.

yeah, thats true