The accusative "contradiction".

[Molly]

I've heard quite a lot of native-speakers use forms such as "Me and her are going on holiday", but I've never heard the same speakers use "me" and "her/him" as single subjects.

Is this quite common, and why is it the case that those people do one thing, but not the other?

[Mister Micawber]

.
A very interesting observation and a true one. I have no idea.
.
_________________
Canadian-American native speaker
who teaches English for a living at Mister Micawber's
ESL cafe: Interview with Mr. Micawber

[Yankee]

.
Well, I've heard occasional jocular use. I knew some people once who had a dog named "Izzer". The dog's name was a result of of the fact that their dog was constantly off gallivanting somewhere, and their constant subsequent question "Where is her?"
.
_________________
Amy
.
ESL teacher, and native speaker of American English

[Haihao]

My wildest guess would attribute the phenomenon to the word 'and'. Without 'and' it has to go like 'He/She is going...' while with 'and' it brings about a sense of preposition like 'with'. Therefore, the orthodox 'I and he/she' becomes 'I and (with) him/her' and then 'Me and him/her' to give a better balance or readability.

Sorry for the rubbish.

[MrPedantic]

"Them" is sometimes used as a subject pronoun ("Them's the jockeys for me!"); in dialect, "us" may be heard as a subject pronoun, and the roles of "he"/"him" and "she/her" may be reversed.

Cf. too the ordinary use of disjunctive pronouns:

1. "I agree with Mister M." "Me too."

Your example might represent disjunctive pronouns + ellipsis:

2. Me and her[, we] are going on holiday.

MrP