Thanks for your questions!
1. Es ist immer noch frei and es ist noch frei are almost exactly the same in meaning - as you say, they would both be translated as "it is still free." The difference is the word immer, which generally translates to "always" and puts a different emphasis on the sentence. While you wouldn't translate it this way, you can think of immer noch as being like "even still" in English.
So basically, es ist noch frei means "it is still free" (with no added emphasis), and es ist immer noch frei emphasizes the "still." It provides a stress on the fact that nothing has changed. It can be used in many different situations, including ones where you would like to imply a bit of impatience (as in: yes, it is still free - same as the last time you asked) - it depends on the context and on one's tone.
2. The difference between eins and ein is that eins is only used when talking about numbers - that is, the digit "one," by itself - and ein is used both as an indefinite article ("a" in English) and when the word "one" is paired with a noun. Ein will change its form according to gender and case - for example, "I have one dog" or "I have a dog" would be Ich habe einen Hund. Eins, however, never changes its form, and you only use it when counting or referring to something's number - for example, Gleis eins is "Platform One."
Note that the number "one" is the only number that will change in case to agree with a noun. The other numbers stay the same (e.g. Ich habe zwei Hunde).
3. Es tut mir leid and Entschuldigung both mean "I'm sorry," but they are used in different ways. Es tut mir leid literally translates to "it causes me pain" and is used when you want to apologize for something with emotion behind your apology. For example, if you get into an argument with someone and realize you were in the wrong, you would say es tut mir leid - in this case, you genuinely feel bad and are, shall we say, "emotionally" sorry. If, on the other hand, you bump into someone on the street, you would say Entschuldigung. In this way, Entschuldigung also means "I'm sorry," but you could translate it as "excuse me" as well. It is not an emotional apology.
4. Kann ich bitte eine tüte bekommen is more literally "Can I get/receive a bag" and Kann ich bitte eine tüte haben is "Can I have a bag"; they are two different verbs, but in this context, they boil down to the same meaning.
Be careful if you are plugging sentences into an automatic translation tool when first learning a language - often, you will get general translations that give you the gist, but you might miss out on the little details. When you're not sure why sentences are coming up with the same translations, try checking each word individually - this will usually get you back on the right track!