I found the answer in the way you can deploy a custom NewForm.aspx page. Deploying modifications to the AllItems page takes the same approach.
Path="CustomAllItems.aspx" (or whatever you named the file)
I faced a similar situation not long ago.
What I did was that I took a copy of the list's AllItems.aspx pasted it into my solution, made the modifications that I needed and then created a feature in which I pointed at the specific list and programmatic switched out the existing AllItems.aspx with my "custom" version of it.