they are a-changin'

To me. it seems to be just a matter of rhythm(as you said), but it(=a-changin') may be more 'literary'.( Here I can't have an opinion right now).

Adding 'a-' before some verbs seems to be older English.   I'm tempted to say it's just used in song (as Rafee said, to fix up the metre), but I'm not at all sure; it only happens before verbs, after all, and it may be just a few selected verbs, so maybe something else is happening.   Is it some old adverbial marker, maybe, as with "away" and "awry" and maybe "against"?   Anyone know?

If it is just an artificial "patch" for the metre of songs, it's kind of like adding '-o' to the end of some lines in the old songs:

There was man he had a dog and Bingo was his name-o....
Green grow the rashes-o

I don't think the same thing is going on with 'be-' before verbs, though.   When you put "be-" in front of a noun, it makes a verb out of it.   To befriend a man is to make him your friend; to belie a statement is to make it a lie; to belove someone is to make her your love.   You can see more of the same with "benight", "believe", "bereave" and others.   It happens that we don't use "belove" any more; the only form left is the adjective made from the past participle, so it looks like it means the same as "loved".

I just looked up a few of those words.   Putting 'be-' in front of nouns goes back hundreds of years; "befriend", for example, goes back to 1550.   But it says here that according to the OED, 'be-' did not originally attach to verbs but was a verb intensifier; apparently they took to putting it on nouns later (but still long ago).