It is possible and quite simple to be honest.
You will need a php file to fetch the data, such as artist name, track title, etc.
Let's say you have a file called "download.php" which will be the main target file to allow the end-user to download the file from your server to their local computer.
A simple download script would look like this (If you're getting data from MySQL):
PHP Code:
<?php
$artist = $_GET['artist'];
$track = $_GET['track_title'];
//Include a connection to the MySQL Database
include("../dbconnect.inc.php"); //Connect File, also change location to the connect file
//We need to perform a simple MySQL Query
$query = mysql_query("SELECT * FROM music WHERE track_title = '$track' AND artist = '$artist' LIMIT 1") or die('Unable to perform the MySQL Query: ' . mysql_error());
$resul = mysql_query($query) or die('Unable to perform the MySQL Query: ' . mysql_error());
$numrows = mysql_num_rows($resul);
//We'll check to wherever the file actually exists in the db.
if ($numrows == 0){//failed
echo "Unable to find the file requested!";
}
//We need to extract some data from the db.
$rows = mysql_fetch_array($resul);
$artist = $rows["artist"]; //These values should be changed to the excate same name in the DB!
$track = $rows["track_title"];
$file_l = $rows["file_location"]; //This will be where the MP3 file is located either file system or DB.
//Now let's get our file.
header("Content-Type: application/force-download");
header("Content-Disposition: attachment; filename=".basename($file_l));
header("Content-Description: File Transfer");
?>
Now you say you want the file name renamed upon download? Here's a simple solution to that my friend.
Open up say Notepad and save this as ".htaccess" and upload it in the same folder where "download.php" is.
Code:
Options +FollowSymLinks
RewriteEngine on
RewriteRule (.*)-(.*).mp3$ download.php?artist=$1&track_title=$2
Then say a user clicked on the url below:
http://www.somesite.com/downloads/boo-hoo.mp3
It would download boo hoo song, jobs a good'n eh? 
Hope this helps!
Bookmarks