Is Stellar permissionless or permissioned blockchain?
or rather (whichever is more adequate)
Is SCP permissionless or permissioned consensus protocol?
It has the properties of both type of systems. The SCP as a protocol doesn't have a central gatekeeper to monitor or ensure validity of transactions. However nodes that do enter the Stellar network work on the basis of shared quorum slices. This means when several nodes have the same value for describing a state, the majority of nodes share the same state value. This acts a pseudo key for nodes to be part of the validating network.
The permission in this context would be seen as a privilege granted to a node to take part in validating a transaction provided it shares the state value with other nodes.
The permissionless context of this methodology is that, any nodes are free to enter the network. However the more reputation or say value a node adds to a network, its seen as a more trusted node.
I'd consider it a decentralized permissioned blockchain. There is no central authority to receive permission from, but the system is based on proliferated trust so you need to get trusted by someone who is already trusted in order for your validation opinions to have any merit.