Wie du schon bemerkt hast, wollen die allermeisten Börsen eine Verifikation, meist mithilfe von Perso Scan... und wie Aswan schon schrieb, hier nutzt bitcoinde als einzige website ein besseres Verfahren. Allerdings nutzen sie beim Verifizieren des Bankkontos dann wieder so einen schrott wie SOFORT (oder Partner die genauso funtkionieren) ...
In erster Linie hängt es davon ab wieviele und wie oft du Bitcoins kaufen möchtest.
1) Willst du regelmäßig coins kaufen, ist die Verwendung einer Börse oder bitcoin.de (ist ein Marktplatz) schon sehr sinnvoll, da es nach erfolgreicher verifizierung sehr einfach und vorallem günstig ist. Falls du dich für bitcoinde entscheidest (mindestkaufmenge 0.1BTC !) ist es empfehlenswert sich das kostenlose Fidorkonto zu holen, da dadurch Trades viel schneller und einfacher gehen und du auch das Problem mit der Bankkontoverifizierung nicht hast (weil Fidor und bitcoin.de zusammenarbeiten)
2) Willst du hingegen nur selten kleine Mengen (unter 100€) ausgeben, dann könnten eventuell "wechselstuben" sinnvoll sein, da könntest du mal
https://www.bitpanda.com/ probieren. Bis zu gewissen Umsätzen verlangen diese keine Verifizierung und man hat mehr Bezahlmöglichkeiten. Dafür kosten die Bitcoins aber auch mehr als wenn du sie auf einer Börse kaufen würdest. In der Regel sind das 1-2% Aufschlag.