How do I rewrite attached file field output in Views to override the filename?
Certainly, you just have to use the correct formatter to start with.  I am guessing that you are using the "Generic Files" one.  If you instead select "Path to File" you can then use rewrite output the way you mention in your question.  Little gotcha:  make sure the title field you are using isn't "linked to its node" or things will get odd :) 

(Note, I am suggesting you rewrite the file field instead of the title field)