It'll take some heavy lifting, but you can do this with the metadata API or ANT.
Step 1 Figure out what components are available
Use a describeMetadata() call to get a list of all metadata component types that are available for retrieval. It'll return the name to use in your package.xml, as well as info about if it's stored in a folder. Unfortunately it does NOT return details about whether the particular metadata component type can be retrieved via the wildcard attribute. You might consider storing a list in your program of what can use the wildcard, or you could just specify the exact name for every instance of each metadata component type.
The Salesforce ANT library also has a a describeMetadata target that returns the same result in text form.
In both cases you can optionally pass in an API version.
Step 2 Retrieve folders for in-folder metadata types
For metadata that is stored in folders you'll need to know the folder before you can get a list of what metadata is in the org. You can do this with a listMetadata() call (supposedly you can do a retrieve call to, but that hasn't worked for me).
To list out the folders, add a "Folder" suffix to the foldered-metadata type, i.e. "DashboardFolder" for dashboard folders or "ReportFolder" for report folders, to get the metadata type and then do a listMetadata() call.
The Salesforce ANT library also has a listMetadata target that returns the same results in text form.
Step 3 List out components for each metadata type
For each component type returned in Step 1 that's not foldered use a listMetadata() call to get a list of all instances of that component in the target org. You could skip this for components that support wildcards, assuming you're storing which support that somewhere.
For foldered metadata types you'll need to make a list call for each folder.
Step 4 Build out your package.xml
At this point you'll have everything you'll need to build out a package.xml.
Step 5 Retrieve your data
Use your package.xml do to a retrieve.
Gotchas Max Retrieval Limit
One thing you'll likely run into if you're doing this with any client orgs is the max retrieval limit. To work around this you can have an intermediate process chunk your package.xml into smaller mini-retrieves. This is normally an issue when orgs have a lot of reports. This gist shows an example done with ruby (warning: ugly code!).