In this case, が is incorrect because you are conveying a known piece of information. When you describe a known or general fact about a subject (お寺), you have to mark it with は, making it the topic of the sentence.
The temple is next to the park.
(This is a known fact to you.)
Birds can fly.
(This is a general fact.)
Note that the subject of the first sentence is still お寺, but now it's marked with は instead of が.
You have to use が when you firstly introduce something in the "universe of discourse":
There is a temple next to the park.
(As a response to something like "Is there a building related to Buddhism around here?")
There is a bird on that tree.
(No one else has noticed this bird before this sentence.)
You have to use が when you report a new event or temporary status you have just noticed regarding the thing marked with が. (neutral-description-が)
The temple is on fire!
(The listener knows which temple you are talking about, but the information ('on fire') is something you just noticed.)
Our/The bird flew away!
(The listener knows which bird you are talking about, but the information is something new.)
In addition, there is something called exhaustive-listing-が. With this, you are choosing and emphasizing something from several possibilities:
It's the temple that is next to the park.
(As a response to "So, what's next to the park is the post office, right?")
Birds can fly.
(As a response to "Which vertebrate can fly?")
This is probably the only case where お寺が公園の隣です would make sense, but if this is too difficult to you now, you can forget this and learn the easier ones first.
My understanding is that there is always a が in a sentence, which may or may not be visible/dropped (zero-ga pronoun) and the subject marked by が may or may not be additionally marked with は.
What do you mean by "the subject marked by が may or may not be additionally marked with は"? You can think は replaces が when the subject is topicalized, but you cannot mark a word with both が and は simultaneously. (は can replace を, too.)
using が here is merely unnatural (and that is what my teacher meant by "wrong") or actually grammatically incorrect
I would say it's grammatically incorrect (for your intended meaning). The distinction of は and が is critically important in most cases. People may guess what you are saying if you are lucky; in this specific case, people will probably understand you, but they never fail to think "Oh, this person is still bad at Japanese." If you are unlucky, it may end up with a severe confusion (example).
Related (if some of my explanation didn't make sense, please read these first):