How can one prove that the union of two finite sets is again finite, without the use of arithmetic?

Suppose to start with that the sets are disjoint. Then prove that if the sets are both finite, and if you remove an element from one set and put it in the other, they are both still finite and their union is unchanged. By induction, you will eventually exhaust one of the finite sets, giving the union of a finite set and the empty set, which is therefore a finite set. Because the union was unchanged in each step, this is equal to the union of the original two sets.

The proof has to be done by constructing bijections between the sets and natural numbers, transferring the element mapped to the last natural number in one set, and mapping it to the successor of the last natural number mapped to by the other.

For the case where the sets are not disjoint you can fix it in several ways, such as deleting them from one set without adding to the other, or proving that removing elements from a finite set always gives a finite result, or using your $B-A$ trick.

If your definition of finite is based on a cardinality equal to a natural number, then perhaps in that sense you would never be free of arithmetic in any such proof.

However an alternative definition of finite could be used that would avoid any explicit reference to cardinal numbers and thus to arithmetic. Such a definition is being ordered so that a set is simultaneously well-ordered in both directions, ie. that any nonempty subset has both a smallest and a greatest element (not necessarily different if the subset has only one element).

In ZFC this definition of finite is known to be equivalent to the usual one, ie. that a set has cardinality equal to a natural number.

Let $A$ be an arbitrary finite set, and assume by contradiction there exists a $B$ which is finite such that the union is infinite.

We have that $B$ is finite, that is there is a bijection of $B$ to some $\{0,\ldots,n-1\}$. So we can assume that this $n$ is the minimal $n$ to have this property.

Choose an arbitrary $b\in B$ (we can do it because $B$ cannot be empty, otherwise the union $A\cup B=A$ and is still finite) then $B\prime = B\setminus\{b\}$ is a finite set whose cardinality is less than $n$ and therefore $A\prime=A\cup B\prime$ is finite by the minimality of $n$.

We have that $A\prime\cup\{b\}$ is infinite, but (this is a much simpler claim) adding one more element to a finite set is still finite, contradiction.