Can SQL Server 2012 FCI have multiple names? Is it possible to have multiple names for the same SQL Server Failover Cluster Instance (virtual server)? IT has a naming convention they like, but it hard codes the Windows cluster name into the SQL Server cluster name, which makes extra client configuration work when we have to migrate servers.

The last time they migrated (from SQL Server 2000 to SQL Server 2005 in 2000 compatibility mode), I think they just added another (DNS) hostname alias, but they only had one FCI. We are now migrating to SQL Server 2012 and we will have two FCIs ("active/active", although I know that's not really the right term), so we can't just use a default instance.

Note that I'm not the one who will be implementing the cluster, but I am migrating the databases and the client software, so I'm making the requests to the guys who are implementing the cluster. I don't want to ask them to do something that can't be done or isn't a good idea.
Consider using Sql Client Aliases to abstract the data source name. The aliases are set on client computers by either adding keys to registry or by running c:\windows\system32\cliconfg.exe (for x86, x64 systems) and c:\windows\syswow64\cliconfg.exe (for 32-bit applications in x64 system). A Sql Client Alias is quite a bit like the additional DNS record you described. What's more, aliases support instance names too, a feature that DNS record won't do.

After an alias has been created, configure the client to use it instead of real Sql Server instance. Should you ever need to change the server, just modify the alias.

As a caveat, there seem to be some applications that won't work well with aliases. These often are legacy ones, like those using ODBC or proprietary database drivers. For modern applications, aliases will work just fine.