Are all prime numbers finite? If we answer false, then there must be an infinite prime number. But infinity is not a number and we have a contradiction. If we answer true, then there must be a greatest prime number. But Euclid proved otherwise and again we have a contradiction. So does the set of all prime numbers contain all finite elements with no greatest element? How is that possible?
 A: Every natural number is a finite number. Every prime number (in the usual definition) is a natural number. Thus, every prime number is finite. This does not contradict the fact that there are infinitely many primes, just like the fact that every natural number is finite does not contradict the fact that there are infinitely many natural numbers. You can have infinitely many finite things, and there won't ever be a biggest exemplar. 
To make things a bit more complicated (and a lot more interesting), there are extensions of the set of natural numbers that do contain infinite numbers, and even infinite prime numbers. For instance, in any hyperreal extension of the reals, there is a system of hypernatural numbers. Some of these hypernatural numbers are finite and some are infinite. The finite ones are just a copy of the usual set of natural numbers and the primes in it are the usual primes. For the infinite hypernatural numbers, there are also prime numbers. For instance, the hypernatural represented by the sequence $(2,3,5,7,11,13,17,19,\cdots )$ is an infinite prime number. 
A: A prime number is an element of the set of all prime numbers, and as an element of that set, a prime number has no cardinality. 
The set of all prime numbers is countably infinite (in cardinality, equal to $|\mathbb N|$): there are (adverb) infinitely many primes. 
That's not to say there is a prime that is infinite. But you are correct that "infinity is not a number" here. The set being "infinite"  means that no matter how large a prime number you name may be, there is yet a larger prime than that...and after that, yet a greater prime, and so on. There is no end point at which you arrive at the largest prime number.
It is true that set of all prime numbers less than or equal to some positive integer $n$ is finite. But there are then infinitely many more primes greater than $n$, whatever particular $n$ you choose.
A: 
Are all prime numbers finite?

Yes.

If we answer false, then there must be an infinite prime number.

That follows ... but we didn't "answer false", so we don't have to worry about it.

But infinity is not a number and we have a contradiction.

Whether or not infinity is a number, there are infinite (or "transfinite") numbers. And even if there weren't, this still wouldn't be a contradiction, any more than "Not all horses are ugly" is a contradiction just because beauty is not an animal. This isn't about logic or math, it's about misuse of the English language. In any case, we didn't "answer false", so we don't have to worry about this supposed contradiction.

If we answer true, then there must be a greatest prime number.

No, that does not follow at all. All primes are finite, but there is no greatest one, just as there is no greatest integer or even integer, etc. That there are infinitely many of something doesn't require that any of them be infinite, or infinity, or greatest.
Consider for instance the non-negative reals less than 1: [0, 1). There are of course infinitely many of them, but they are all finite (less than 1, in fact), and there is no largest one. (Proof: suppose there were a largest one, L. Then (L+1)/2, which is halfway between L and 1, would also be in the set but would be larger than L. That really is a contradiction.)

But Euclid proved otherwise and again we have a contradiction.

He did, but there is no contradiction.

So does the set of all prime numbers contain all finite elements with no greatest element?

Yes.

How is that possible?

There's no reason for it to be impossible, and Euclid proved it not only possible but true. You appear to have assumed it impossible in order to reach your conclusion of a contradiction, which is a circular argument.
A: You can have an infinite number of objects, each with finite size, the sequence of which is not bounded, so yes all primes are finite... by definition of a prime number almost. It's meaningless to talk about a natural number being 'infinite' until you define that term.
A: The modern definition of an infinite set is one which can be expressed in a one to one relationship with a subset of it self: eg: 2 4 6 8 and 1 2 3 4. this video produced by bbc horizon explores infitity, why there are at least two sizes of infitity... yup and many more aspects of infinity and its very wachable too... http://www.youtube.com/watch?v=FiMigmLwwTM
The answer to your question is that you question is not a correctly stated mathematical problem in the english language. You are mixing up values within a set and the number of values within that set.  
This response was written before the question was edited. Still recommend the video though. 
A: The answer depends on what you mean by number and in fact there are infinite prime numbers if and only if there are infinite numbers, by the tranfer principle. Namely, consider the first order statement that for every $n$, there is a prime $p$ greater than $n$. By transfer this is true for all $n$ including a particular infinite $n=H$.  But any prime $p$ greater than $H$ would also be infinite.
