Prior to Phillip's time, the ancient Greek world was fragmented in (often warring) city states and kingdoms, and citizenship was considered far more important than nationality or ancestry. Pericles' reforms (451 BC) exemplify the distinction: From that point on Athenian citizens would lose their citizenship if they married non Athenians, regardless of their Hellenic ancestry. Similar laws, more or less, existed in Sparta, Athen's cultural and political counterweight, and all around the Ancient Greek world. In a comparably similar manner, both Philip and Alexander favoured the citizens and soldiers of Macedon over the rest of the Greeks.
The first time the Greeks became a single political entity, with the notable exception of Sparta, was the League of Corinth (337 BC). Thus the concept of Greek nationality was just one year old when Philip was assassinated and the 20 year old Alexander assumed power. However his ancestry had been considered Hellenic since the times of Hesiod and Homer and his dynasty had been recognized as ethnically Greek since at least the Graeco-Persian wars.
Simply put, ancient Macedonians were one of the many Hellenic tribes. What bonded them with the other Hellenic tribes - the Minoans, Achaeans, Ionians, Mycenaeans, Dorians, and Epirots to name a few - was a cultural and historical bond, not a national or ethnic one. The Macedonias spoke in a Greek dialect, worshipped the gods of Olympus and followed all major traditions of their fellow Hellenes. If we approach the question strictly from a cultural perspective, the answer is obvious: ancient Macedonians were decisively Greek.
There's an abudance of archaeological evidence for the above in Dion, the Macedonian sacred city. Dion was build in the feet of mount Olympus and early in the 5th century it became the cultural and religious centre of the kingdom of Macedon. Archelaus I of Macedon created a sanctuary in honour of Zeus and re-organized and brought to prominence a nine days festival (the Olympia) in honour of Zeus and the Muses. Every major city state of the era build their own sanctuaries in Dion - some still visible - and participated in the festivities.
The Greeks weren't particularly xenophobic, but they never participated in barbarians' religious festivities or allowed barbarians to participate in their own. It only takes a short walk through the ruins of Dion to quickly realize the Macedonians were widely accepted as Greeks by the other Hellenic tribes.
Hesiod on the origin of Macedonians
Hesiod (750 - 650 BC) gives us a beautiful story of the origins of Macedonians, in Catalogue of Women. According to his mythology, Macedon was Hellen's nephew. Hellen was the mythological progenitor of the Hellenes and where the words Hellas and Hellene come from. This mythological relationship binds Macedonians with the other major tribes of the era:
The Hesiodic mythology is our basis for which tribes of the era can be considered Hellenic. If we doubt the Macedonians' belief that they were Hellen's descendants, I don't see why we don't doubt the similar beliefs of the rest of the Hellenic tribes.
Herodotus on the origin of Macedonians
The royal house of Macedon claimed an Argive1 descent, tracing their origin to the legendary Hercules2. Herodotus presents the claim in his Histories, by describing an event that took place prior to the naval battle of Salamis (492 BC). Alexander I of Macedon, while visiting the Greek camp as an envoy for the Persian general Mardonius2, proclaims his Greek ancestry:
[Hdt. 9.45.1] Hearing that, the generals straightway went with the men to the outposts. When they had come, Alexander said to them: “Men of Athens, I give you this message in trust as a secret which you must reveal to no one but Pausanias, or else you will be responsible for my undoing. In truth I would not tell it to you if I did not care so much for all Hellas;
[Hdt. 9.45.2] I myself am by ancient descent a Greek, and I would not willingly see Hellas change her freedom for slavery. I tell you, then, that Mardonius and his army cannot get omens to his liking from the sacrifices. Otherwise you would have fought long before this. Now, however, it is his purpose to pay no heed to the sacrifices, and to attack at the first glimmer of dawn, for he fears, as I surmise, that your numbers will become still greater. Therefore, I urge you to prepare, and if (as may be) Mardonius should delay and not attack, wait patiently where you are; for he has but a few days' provisions left.
[Hdt. 9.45.3] If, however, this war ends as you wish, then must you take thought how to save me too from slavery, who have done so desperate a deed as this for the sake of Hellas in my desire to declare to you Mardonius' intent so that the barbarians may not attack you suddenly before you yet expect them. I who speak am Alexander the Macedonian.” With that he rode away back to the camp and his own station there.
The Greco-Persian Wars and Herodotus' account are significant because this is the first time in Greek history the Greeks united, even if only to face a common enemy. The Argeads claim of Greek ancestry was successfully put to the test 20 years after the battle of Salamis, when Alexander attempted to participate in the Olympic Games (500 or 504 BC):
[Hdt. 5.22.1] Now that these descendants of Perdiccas are Greeks, as they themselves say, I myself chance to know and will prove it in the later part of my history. Furthermore, the Hellenodicae who manage the contest at Olympia determined that it is so,
[Hdt. 5.22.2] for when Alexander chose to contend and entered the lists for that purpose, the Greeks who were to run against him wanted to bar him from the race, saying that the contest should be for Greeks and not for foreigners. Alexander, however, proving himself to be an Argive, was judged to be a Greek. He accordingly competed in the furlong race and tied step for first place. This, then, is approximately what happened.
The Greeks contesting Alexander's ancestry was most probably politically motivated. Macedonia was a Persian puppet state during the Graeco-Persian wars, and it's not unreasonable that the Greek world was uncomfortable with a Macedonian competing in the Games. Still, the Hellenodicae ruled in favour of Alexander and it should be noted that Archelaus I had also competed in the Games prior to the Persian invasion.
In recent years, starting from the late 19th century and onwards, there have been various efforts to question Alexander's ancestry and essentially rewrite history. Most of these efforts are related to the often bitter Macedonia naming dispute. This complicated political issue has produced tons of documentation, from both sides, and the politically charged rhetoric is where the historically false dichotomy of Greek or Macedonian comes from.
1 From the Peloponnesian city of Argos.
2 The inscription "ΗΡΑΚΛΗΙ ΠΑΤΡΩΙΩΙ" (Father/Ancestor Heracles) was found in one of the rooms of the palace in Aegae, the Macedonian capital.
3 Mardonius had quickly subjugated the kingdom on Macedon, during the Persian invasion of Greece.