In general, you should practically never have trait bounds on type parameters of data structures.
I guess this kind of makes sense to me now. Though I have to say that defining the WriteCommand struct with a generic, unbounded type bins member still feels very wrong. After all, there are very tight constraints on the bins type, so shouldn't those be declared on the struct definition and not just the impl block? It's not relevant in this particular case, but wouldn't this also potentially cause problems with the API documentation, where the docs for the struct do not specify the expected member type?
In the end, though, I had to give up on the Iterator-based solution for a different reason. In the real code, the execute function needs to iterate over the bins twice: Once to determine the overall size of the bins and to allocate a sufficiently-sized buffer; then once again to actually serialize the bins into the buffer. I don't think that's possible with an Iterator. So instead I'm back to using a Bin slice and am using just AsRef to allow both owned and referenced Bins:
fn put<A: AsRef<Bin>>(&self, policy: &WritePolicy, key: &Key, bins: &[A]) -> Result<()>
(Another suggestion from the original post.)