We have had a couple of papers rejected from conferences quite a while ago, and we now would like to post them in arXiv. We are considering indicating on the paper which conference it was rejected from, mostly to state when the paper was actually written (we are also writing a new paper with additional results). Is this an acceptable practice?
No, you should not do that. Rejections are not to be advertised. Everyone who will read the paper will be prejudiced against it and you simply do not want that. After all, many papers are initially rejected before being accepted at a suitable venue. You want other people to know when your work got finally accepted and not the other way around.
If you want to establish the initial date of the paper, next time I would suggest to upload immediately after rejection and after addressing the reviewers' comment that lead to your rejection. This way, you have a better paper uploaded, you establish priority before submitting to the next conference and you can cite your work in subsequent publications.
There's no real reason why you can't. Unless the conference organizers explicitly asked you to agree to a nondisclosure agreement, which would be very surprising indeed, there's nothing stopping you from doing it. The conference organizers will probably be weirded out by it but little more.
There's also no reason why you should. Nothing sets negative expectations like you saying "Hi! Here's a paper that [respected academic committee] found unsatisfying." It sets a negative tone that will be very hard to undo with the paper, for no benefit at all.
Think instead of why you want to do this. Is it to associate the paper with the conference? That will simply not work. Is it to indicate the sort of area you think the paper belongs to? There's a much better way: say it directly, most importantly by your choice of arXiv category, keywords, and abstract.
If what you want is to indicate when the paper was written, simply say that! Add a single line, in small font, below the abstract (or a comment to the arXiv submission) saying
This paper was written on -----, with minor revisions before the arXiv submission on -----.
If you ever need to actually prove this, say, because of a priority dispute, you can then contact the conference so they can confirm it.
If what you want is some form of authoritative datestamp on the date the manuscript was written, it won't work and it is not the right metric anyway. It is not a credible way to establish priority as it is still your say-so; very little other than confirmation from the conference will really convince outsiders that your claim is in fact true.
More importantly, the date that really matters for the academic community is the date the manuscript was made public. If you write a result but then sit on it for a year, no one can make use of that result. As far as other researchers go, the result does not exist until you upload it, so even if you can prove that you discovered independently from some other group that published before you uploaded but after you wrote the manuscript, they still get the credit because they made the result available.