This isn't the question of whether a Cleric/Inquisitor/Paladin/Warpriest in Golarion can function without a deity -- that's already been answered in the negative (with a possible exception for Paladins -- information on them on these forums seems to be contradictory).
This also isn't the question of whether a Cleric/Inquisitor/Paladin/Warpriest can worship a deity that nobody else in Golarion knows about -- the answer to this is also no, with possibly a few exceptions specifically carved out in the Pathfinder Campaign Setting and Adventure Paths.
This question is about whether it is possible for a Cleric/Inquisitor/Paladin/Warpriest to be unable to determine who their patron deity is, and yet function. Not because they are unperceptive or lacking in attempts to determine what they belong to, but because their patron deity wishes to remain hidden from them for now, even if the existence of said patron deity is well known to most people on Golarion, including the divine spellcasting character.
In other words, one day, the character wakes up and finds out that they now have the powers of a Cleric, Inquisitor, Paladin, or Warpriest, and can't figure out where these powers came from, and a visit to the doctor is unable to diagnose any Oracle's Curse whatsoever.
Naturally, the default character class for such characters would be Oracle (which doesn't even have to be tied to just one deity), or possibly Shaman or Witch (but that is arcane anyway), but I could see situations in which a patron deity might want to prepare some kind of specialist, and/or consider the path of Oracle otherwise unsuitable for the development and trial a particular minion.
One potential mechanical sticking point is the requirement of these classes for a holy symbol for divine casting; most of the ways to get around this require already having some levels. A more minor point for some of the classes is that becoming proficient with a deity's would help the character narrow down the list, assuming that the character had not already gotten the proficiency from racial proficiency or levels in a martial class. Although the latter problem could make for some more interesting roleplaying opportunity -- 'I'm really good with a Greataxe without having been trained with it, and just who has that as their favored weapon -- Angradd?, but I'm not a Dwarf, and he doesn't take non-Dwarves; Damerrich?, but I'm not the judicious type, and despite all efforts I don't think I'm anywhere near good enough for Damerrich; oh $#&%, that leaves only a Draconic Malebranche, several Demon Lords, and Rovagug . . . and the doctor did say that I have Qlippoth blood in me . . .'.
Under these circumstances, I probably would treat the proficiency as something that did require training, and thus wouldn't grant it. I don't know if this is possible in "canon" Golarion, but I doubt it. This is exactly what they made oracles for, after all. :)
In 3.5's Exemplars of Evil, there was a priestess of Corellon who ended up body-switched with a priestess of Lolth. She still thought she was worshiping Corellon; however, since her only domain was Chaos (which the two share), Lolth eventually took over her spell-granting as she slipped into psychosis. It was really interesting. :)
^Oracle is great for that . . . except not for certain concepts. Especially concepts involving a character whose racial bonuses don't include Charisma, or worse whose racial penalties include Charisma. Also concepts where a different type of specialist is needed. (You'd think that deities would see the benefits of diversification.)
Well... I'm guessing they do. That's why they have clerics and warpriests training at their temples. :)
I just don't think it's something that happens in the campaign as written. I can't think of any time in all of Pathfinder that this has happened. The oracle, and to a lesser extent the witch and sorcerer, have a pretty firm hold on this conceptual niche.
Also, I suspect dwarf oracles show up more often than you'd think, stat penalties be damned. We've seen on multiple occasions that the world of Golarion is nowhere near as optimized as the forums. The iconic druid has a racial penalty to Strength and a bonus to Charisma, after all. :)
That being said, you may want to check out the chosen one paladin archetype. I think it might be of interest...
Sound like a fantastic concept to me. There are a few ways, mechanically, you can go with this, and it's kind of a pity that PF/Golarion has stolen so much flavor from the Cleric/Warpriest/etc. . . to make the Oracle/Sorcerer/Bard concepts.
If your character doesn't know what patron they follow, consider walking around with a handful of holy symbols. They are cheap, so shouldn't even be an issue at level 1.
As for the weapon proficiency, unless it's a weapon that only one Patron deity offers, think about it more in the terms of that deity picked you because you already favored using that weapon, and instead had been giving you a bit of divine favor from an early age. Similarly with the idea of following their philosophy and worship. Something to keep in mind is that in Golarion, "worship" is along the lines of doing things that spread and increase a particular deity's portfolio and sphere of influence in the world, not just acts that are done specifically in that deity's name or for their cause.
So, this means that, for example, all the acts of battle, killing, and war that a saintly crusading warrior priest of Iomedae does in the Worldwound are equally acts of "worship" to beings such as Rovagug (destruction, death), Gorum (battle, war, tactics, conflict), Abadar/Asmodeus (bringing order), Pharasma (it was their time), and Nethys (magic is magic, no matter what it's used for), as well as for Iomedae who the individual follows.
Now, the minor issue is you do need to pick one deity as your patron, at least as a player, and keep that in mind, even if your character doesn't know for sure, and you can also reinforce this with the character receiving false visions from others deities, especially those with the same Favored Weapon and/or weapon.
I have a character that's similar to this in PFS. Technically, as in on the character sheet only, he is a Cleric of Sarenrae. But for backstory, he is literally the child of a special encounter between Sarenrae and Ragathiel, and as an Aasimar, he wasn't really ever born, as much as just kind of came into existence.
Rules wise, he has Sarenrae's Domains and favored weapon, but holds himself up to both of their ideals and rules. When he speaks of them, he calls them "mother" and "father", or by titles of endearment he has given them, never by name.
And when I play them, I leave it up to individual DM's as far as the validity of his claims. He is either speaking the truth or if a DM has an issue with it, than we can say out of character he is insane, and while he honestly believes this, it's not the truth, and leave it at that. It doesn't alter the way he I played or RP'd at all. It doesn't alter his personality.
It's one of the best, in the sense of my favorite to play, Clerics I've ever played in PF. Especially as I personally detest the "all Clerics need a Patron Deity" for how stifling it is to character concepts. It's one of the worst cases of "the DM" saying "No!!! you can't." instead of what they should have said, "Yes, you can, but. . . ".
I don't mind the general Pathfinder Campaign Setting rule about Clerics/etc. -- it gives structure to the setting and its divine classes. But structures are generally better when they have service entrances and emergency exits . . . .
The Chosen One Paladin archetype is an interesting concept, although the addition of a Familiar doesn't fit the flavor of all of the concepts that might want to mesh with this. Still, it would be interesting to have Chosen One/Hidden One archetypes of the various divine classes.
To me it's a question of, "How active does one have to be to get the attention of a divine source of power?".
I have no problems seeing an unknown entitiy supplying the juice for Oracles and Divine Sorcerers/Bloodragers/Magus types. To a lessor extent I can envision a deity acting as the hidden benefactor to Paladins, War Priests, Witches, and Inquisitors who embody their cause. I don't see why a deity couldn't imbue someone without the recipient asking for the power it first.
A Cleric not being about to figure out who's empowering them is harder for me to fluff off to myself. I personally have always viewed a Clerics as having a more intimate nature with their deity and having to jump through more hoops than other divine classes to get their abilities. To me a Cleric has to actively pray and petition a Force to empower them. It's hard to ask someone for something when you're not aware they exist to be asked in the first place. I suppose a god could answer an unaddressed prayer, but I have difficulty accepting it developing into a full on Cleric-Patron for any length of time. Also a Cleric who's a member of a Mystery Cult worshiping an unknown deity might work out.
The issue with that is that its really not a supported concept at all. Clerics do not get any special benefits (mechanically) for it. It was not a part of the original class concept, (and in fact originally there where no named god/gods), and it really is jut one interpretation of the possibility for the class. But within the context of how the rules and fluff line up, it makes no sense.
Why would any deity empower anyone, when there are Oracles and Divine Sorcerers and Witches who an do all the same stuff and more? All can be priests, too. Why do all the extra work for no benefit? I mean a Sorcerer that acts grossly violates the deities beliefs while acting in their name is going to come up on the radar too as an issue.
They may not loose powers, (though a Cleric might not either), but such an individual is still going to either be a problem the deity is going to have to deal with, or one the rest of the faithful are going to need to put down.
As written, the setting also does not enforce any sort of divine inspiration or wisdom on a Cleric's part. That is, almost no nation relies on Clerics as spiritual advisors, courts don't bow to the churches, and rulers don't restrict themselves because a spokesperson of the deity tells them no. Or, in the few cases they do, it's no different than if a Wizard, Oracle, Shaman, Druid, Witch, or false priest was in their place, and just a likely, if not more that that is the case.
If the Cleric/Paladin class is supposed to be the hand and voice of their deity, than the setting and the mechanics need to reinforce that, but they do not. There is no sacred or profane bonus to social skills to influence the world in the deity's name, or anything that gives them divine legal immunity, for example. Thy are just like the next guy/gal, just happening to use divine magic instead of arcane, or special know-how and tricks with skills or weapons and arms.
That's why it makes more sense to me to not have that bit of fluff enforced at all, and instead to look at Clerics and Paladins as individuals that study and focus on mastering divine/spiritual mysteries rather than being "granted" powers. They empower themselves by living up to their self-imposed ideals, similar to the basic idea of a Monk or Jedi, the harder they train, the more they stick to their regiment, study wisdom and knowledge, and live by the deeper spiritual beliefs, the more they advance along that path.
It's when they turn away from them, and because they are, by definition, self-imposed, when they betray those beliefs and themselves by taking the wrong course of action, or the easy path, it's that blow to their own conscience and sense of true failure that restricts their powers.
The mechanics are the same, a Cleric that acts poorly or misused their power begins to loose those powers, but it also lines up much better with the flavor and offers a much more heroic view of the Cleric & Paladin. They are individuals who have earned their abilities, not little slaves that a deity just gives them.