Since sometime in 2009, if you have proficiency in an implement type from any source, you can use that implement with any power that has the implement keyword.
The easiest MC for a cleric to qualify for that provides Staff implement proficiency is Acolyte of Divine Secrets (mc invoker), which requires 13 wisdom and gives you access to staves and rods, as well as Hand of Radiance, which is exceptional for minion popping. The wasted duplicate training in religion is sad, but hardly a deal-breaker.
Sentinel Initiate is another option, at the same requirements, providing you with nature training, staff proficiency, and a 1/day extra healing word in an encounter.
MC Wizard does also work here, but your INT is probably not attack-calibur, so the at-will-as-an-encounter power is substantially less of a draw on that end.
Clerics start with proficiency in staves as weapons (they're a two-handed simple weapon), and yes, quarterstaves can be used as staff implements and staff implements can be used as quarterstaves. Keep in mind that you can use staves as implements in one hand, but you will need to hold it two-handed to make weapon attacks with it. This is only an issue if you wanted to hold a shield or second implement in your off-hand.