...
- Combat zones (choosing the right faction): does this work?
- Killing wanted ships in a RES (?? if station nearby is owned by the right faction??): does that work?
- Mining and turning in at the right station? (How fast is this?)
- Trading and turning in at the right station (How fast is this?)
- Other suggestions?
(tips on how to improve influence, would also be a really nice fit in the first post of this thread)
...
Since I enjoy doing missions, I do missions.

Usually it takes 2-3 days with ~3 hours each for me to become allied via missions, depending on the missions offered ofc.
Missions with "high" reputation reward work best, hence Kill/Combat Zone/Assassination missions are the fastest/best way to go.
For me handing in bounties worked good: ~2,5 Mil for friendly, ~5 Mil for allied
So if there is a RES in the system this is the fast way. Be careful since some factions that grant a permit are pirate/unfettered factions so don't kill any on them.
Trading should to the job too but you have to sell your stuff at a station that is controlled by the permit granting faction.
Limoncello Lizard had good success with mining.