How do I allow users to use their own domains as their profile URL?

Question

I have a website where every user has a profile with a URL of the type www.site.com/username123. Now, I want to allow each user to use their own domain like www.username123.com that points to your profile.

Tumblr does exactly what I want (screenshot below):

Assuming I’m using PHP and Apache:

1. What kind of server do I need? Can I use shared hosting?
2. What settings I need to make on the server?
3. What type of DNS record the user needs to create to work?