Any of the cloud providers are great for this. You can start with a free micro image from Amazon maybe during development phase if you have to start dirt cheap, and go up from there. Any of the cloud providers will let you scale as far as you need. That part is a no brainer.
"Thousands of users" is a little vague. Depends totally on how many of them are active at the same time and intensive is what they are doing. I would think potentially something like a small 1 gig image might handle this in the low end scenario (not everybody interacting simultaneously). That does not sound scary.
What ever development stack you are most comfortable with should work. I don't see why Java would be a bad choice. Its probably not the first choice of many.