I understand your design goal, but I see an issue in that you propose to encrypt the metadata alongside the passwords. Searching is made more complicated because you have to decrypt the database to expose the metadata to search for the associated password.
Instead, consider storing only encrypted, unique passwords in your database, indexed by a secure hash of the site/username metadata. For any new site that requires a password, locate a slot indexed by $H(meta)$. Generate a unique password for that site, encrypt it with the master, and store it at the hash slot. Give the plaintext to the website.
To access the password later, reverse the steps. This lets you encrypt only the passwords, and uses a strong hash function to protect the mapping between the site and the password even in the event of a disclosure of the master password.
[A few edits later,] Here is a protocol that might work. It assumes you have a secure hash function $H$, a wallet $W$ indexable as a dictionary with no entries to start, and a secure master password $m$. Assume $E_p(data)$ means to encrypt data with key $p$, and $D_p(data)$ means to decrypt. Let $meta$ be a tuple representing the site name, user name, cookie, or anything else that makes sense to include for retrieving a password.
When visiting a site $s$:
- Let $i \leftarrow H(meta)$.
- If $i \not \in W$, then this is the first visit to the site (with this meta tuple); generate unique password $p_s$ (conforming to the policy at $s$) and encrypt with $E_m(p_s)$ and store at $W[i]$.
- If $i \in W$, then site has been visited before, therefore retrieve site password $p_s \leftarrow D_m(W[i])$.
The benefits are that you decrypt only a single password for each site $s$. The master password $m$ is used only for site password protection, not for the metadata. The identity of the sites and meta information are protected with a hash function. With a fast implementation of $W$, lookup can be as fast as $O(1)$. A dictionary indexed by a hash can grow dynamically, better than my previous edit.
On the downside, if the adversary has access to $W$ and meta information on $s$, he can tell that you have an account on that site. By encrypting the entire database including metadata, your original design is secure against this threat.
I haven't thought more than a day on this, so there may be a weakness - hopefully someone will comment and I'll continue to revise it.