Just glancing at it, this:
template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
if ((last - first) < 3) {
return;
}
...jumped out--although the template parameter seems to imply that you want this to work for bidirectional iterators, the subtraction will only work for a random access iterator. To work for bidirectional iterators, you'll want to use std::distance instead.
Although it's only in the test code:
std::ostream& operator<<(std::ostream& out, const std::vector<int>& v) {
if (v.begin() == v.end()) {
return out << "{}";
}
...I'd prefer if (v.empty()) {
As far as the algorithm goes, yes, there's better. In particular, it looks like your current algorithm is \$O(N^2)\$, but it's possible to do the job in \$O(N)\$ (as you probably expected).
The first step would be to reverse the entire second half of your input. From there you can use an in-place shuffle algorithm. Also see an old answer on SO.