Can a matrix $A$ commute with $e^B$ without commuting with $B$?

Yes, this can happen.

Take $B$ to be diagonal, with entries $2\pi i k$ with different $k$ (so that $B$ is not a scalar matrix). Then, $\exp B = 1$, so it commutes with anything.

Now, since $B$ is not a scalar matrix, there is some $A$ that doesn't commute with $B$.

Referring to your question in the comment to @lisyarus, if $A,B$ are hermitian then $\left[A,e^{B}\right]=0\Longrightarrow\left[A,B\right]=0$.

To see this, observe that two hermitian matrices commute iff they can be simultaneously diagonalized. Thus, if $\left[A,e^{B}\right]=0$ there exist a unitarian $U$ such that both $U^{\dagger}AU$ and $U^{\dagger}e^{B}U$ are diagonal. Now

$$U^{\dagger}BU=U^{\dagger}\ln e^{B}U=\ln\left(U^{\dagger}e^{B}U\right)$$

is also diagonal and therefore $\left[A,B\right]=0$. Note that indeed

$$B=\ln e^{B}$$

since in the diagonal basis this translates to $\lambda_{i}=\ln e^{\lambda_{i}}$ where $\lambda_{i}$ are the real eigenvalues. This fails for non-hermitian matrices because in that case $\ln$ is multivalued and not injective.