To describe and simulate dynamic micromagnetic phenomena, we consider a coupled system of the non-linear Landau-Lifshitz-Gilbert equation and the conservation of momentum equation. This coupling allows one to include magnetostrictive effects into the simulations. Existence of weak solutions has recently been shown in Carbou et al. (2011) (Global weak solutions for the Landau-Lifschitz equation with magnetostriction. Math. Meth. Appl. Sci., 34, 1274-1288). In our contribution, we give an alternate proof which additionally provides an effective numerical integrator. The latter is based on linear finite elements (FEs) in space and a linear-implicit Euler time-stepping. Despite the nonlinearity, only two linear systems have to be solved per timestep, and the integrator fully decouples both equations. Finally, we prove unconditional convergence-at least of a subsequence-towards, and hence existence of, a weak solution of the coupled system, as timestep size and spatial mesh size tend to zero. We conclude the work with numerical experiments, which study the discrete blow-up of the LLG equation as well as the influence of the magnetostrictive term on the discrete blow-up.