Most banks will not forge any partnership. Depending on which country of the world you operate in, financial regulators may prohibit the bank from investing in your startup in any manner.
The bank, first and foremost will always concentrate on their business. If you fit into their traditional business channels, they will work with you. This is what banks do best. They provide (sometimes even extend) their banking platform which includes financial services to businesses to build upon them.
Since they are the only ones who are licensed to handle money, the bank will always see how your product offering can fit into their scheme of things.
To specifically answer the questions you asked:
1. A deal is attractive to the bank when (a) it is compliance with the regulator (b) the Risk Officer of the bank has deemed it to be less risky (c) it is in play with their current product offering (d) it does not downplay or dilute an existing product offering
2. The Who is almost one of the easiest part, yet, the one that most people screw up with. You have to be cognizant of the banking verticals and under which department would your product offering come under. Very rarely would a product offering over lap with two departments. Anyhow, find out which department can sponsor/lead the initiative and then speak to the Head of Department. A common mistake is for people on the outside trying to figure out who in the bank would be responsible for leading the effort. If the HOD of a specific vertical sees potential in your offering, they will channel it to all the right places.
3. Banks as I cited earlier, don't put much play into "partnerships" in the literal sense. What they are more interested in, is the likelihood of making money by what you have to offer. So, they are interested in the topline, bottomline and everything in between. You first and foremost have to tackle the Legal/Compliance angle. Without this being tackled, there is no going forward. Then, how much business can you throw their way in a given year. Don't worry, they will figure out how much money they will make from it. You just have to be confident of throwing business their way. Lastly, what value add do "you" bring to the table. If the bank sees synergy in your offering, they will very easily be able to work with you to white-label your product(s).
4. As cited above, most banks will NOT do partnerships (of any kind). They will however offer a listening ear for white-labeling of services.
Best of luck in your endeavor.