Redirect all subdomains to subfolders

Which DNS providers allow me to do this?

All competent ones. It doesn't even need to be a DNS-specific providing, most good hosts will help you with this too. There are two stages:

1. A DNS entry is added for *.example.com
2. The host's web server (e.g. Apache) is setup to respond to *.example.com by routing it to example.com's VirtualHost.

Then, at your end, you add a .htaccess entry that uses a RewriteRule to catch each subdomain, and redirect it to a folder using the HTTP_HOST variable.

Untested, but something like this:

RewriteEngine on
RewriteCond   %{HTTP_HOST}                 ^[^.]+\.example\.com$
RewriteRule   ^(.+)                        %{HTTP_HOST}$1          [C]
RewriteRule   ^([^.]+)\.example\.com(.*)   http://example.com/$1/$2

Suppose that the user requests app1.example.com/bob.

Line 2

This will catch app1.example.com in the HTTP_HOST - it'll match the RewriteCond.

Line 3

Normally, Apache will only pass /bob to be checked against the RewriteRule. To use the subdomain, we exploit Chaining by forcing the next rule to match

${HTTP_HOST}$1
|           ^ /bob
^ app1.example.com

Line 4

The final RewriteRule is now matching against app1.example.com/bob and not just /bob. As a result, it can have a 'full' regular expression to match both this subdomain and the path, and perform the desired redirect.

If you don't want this feature, you can simplify the rules.

Are these alternatives feasible? Redirect them all to a special webapp with a static IP that redirects to the proper subfolder. How can I know from which subdomain they came from?

There is no sure-fire way of doing this. You could try the HTTP Referer, but it's not always sent by all browsers, some firewalls remove the header, etc.

Programatically create each rule when I need it. Which DNS providers have API access to add rules? I think Amazon Route 53 might be the answer here.

This would actually result in a more complex solution to the above, so I wouldn't recommend it. It would also create a delay: DNS caches would need to update and certain visitors wouldn't be able to use the subdomain immediately until they do. At least with my suggestion above, they'd be able to get going instantly.