Exploiting on-device data and computing power for machine learning at the network edge is challenged by constrained device resources, privacy requirements, and local data heterogeneity. To address the above gap, this work proposes a dual-functional blockchain framework named BagChain for bagging-based decentralized ML. BagChain integrates blockchain with distributed ML by replacing the computationally costly hash computing in proof-of-work with ML model training and validation, and does not rely on any trusted central servers. Individual miners in BagChain train base models by using their local computing resources and private data and further aggregate these base models, which could be very weak, into strong ensemble models. More specifically, we design a three-layer blockchain structure and associated generation and validation mechanisms to enable distributed ML among uncoordinated miners without revealing raw data. To reduce computational waste due to blockchain forking, we further propose the cross fork sharing mechanism for practical networks with lengthy delay and limited bandwidth. Extensive experiments illustrate the superiority and efficacy of BagChain when handling various ML tasks on both independently and identically distributed (IID) and non-IID datasets. BagChain remains robust and effective even when facing resource constrained mobile devices, heterogeneous private user data, and limited network connectivity. The source code of BagChain is released at: https://github.com/czxdev/BagChain.