I like uberspace. First month is free and you can chose yourself how much you want to pay per month. 5€ per month is the suggested fee but you can pay as little as 1€.

you get full ssh access and can do almost whatever you like.