Declaring a diplomat a Persona non Grata is a standard act in international diplomacy. And it is not uncommon. Article 9 of the Vienna Convention on Diplomatic Relations, the "rulebook" of international diplomacy, explains what this means:
The receiving State may at any time and without having to explain its decision, notify the sending State that the head of the mission or any member of the diplomatic staff of the mission is persona non grata or that any other member of the staff of the mission is not acceptable. In any such case, the sending State shall, as appropriate, either recall the person concerned or terminate his functions with the mission. A person may be declared non grata or not acceptable before arriving in the territory of the receiving State.
If the sending State refuses or fails within a reasonable period to carry out its obligations under paragraph 1 of this Article, the receiving State may refuse to recognize the person concerned as a member of the mission.
There is just one caveat: The EU itself didn't sign the VCoDR. But all its members have. Also, the EU exchanges diplomatic missions with over a hundred different states, and these diplomatic exchanges generally play by the rules of the VCoDR. So one could reason that the VCoDR simply became customary law for the EU.
So yes, the EU can generally do that. But who in the EU can do it?
According to Article 15 of the Treaty of the European Union, external representation and foreign policy is generally the domain of the European Council, which consists of the government heads of the member states of the European Union. They do not necessarily need to ask the Parliament for permission to act in that domain. So the Council would consider the open letter by Gianni Pittella a suggestion they might or might not act upon.
Regarding Mr. Malloch's personal immigration status: Above reads "recall the person concerned or terminate his functions with the mission". If Mr. Malloch's function would be terminated (or rather not assigned in the first place), it would not have any effect on his immigration status. "Persona non Grata" only means that he needs to stay away from any diplomatic business and that he loses whatever rights he had due to diplomatic status. If his only legitimation for residing within the EU would have been diplomatic status, he would need to leave. But considering that he is already residing in the EU despite not being a member of any diplomatic mission, he apparently would not need diplomatic status to continue to do so.